Лучший алгоритм сортировки экзаменов

Question

Я грейдер для курса статистики и получаю ряд заданий на бумаге, которые мне дают в случайном порядке. Часть моей работы состоит в том, чтобы расположить их в алфавитном порядке. Я использовал метод, подобный быстрой сортировке, но другие грейдеры использовали другие методы. Я хочу эффективный метод сортировки с обоснованием, когда у меня «большое» количество экзаменов с предоставлением обоснования. Вот некоторые особенности, которые я использовал:

• У меня есть список, который содержит алфавитный список всех имен, которые я должен увидеть.
• Мне все равно, чтобы имена были в алфавитном порядке, а не только первая буква. Например, я в порядке, если «Смит, Джон» предшествует «Солк, Джонас».
• Мне никогда не придется сортировать более 300 объектов.

До сих пор мой метод заключался в том, чтобы найти медиану последней буквы (т. Е. Если есть 60 листов, выбрать букву фамилии, соответствующую 30-му человеку) из списка классов, обработать его как опорную точку и поставить все буквы выше медианы в одной стопке, а все буквы внизу в другой. Если буква совпадает со средним значением, я помещаю ее в срединную стопку. Теперь я делаю то же самое на сваях выше / ниже среднего. Когда стопки достаточно малы, чтобы в стопке было только три или четыре буквы, я делаю одну стопку для каждой буквы, затем складываю стопки в мастер-стопку в алфавитном порядке.

Существуют ли какие-либо алгоритмы, специально предназначенные для алфавитного оформления, или что-то более эффективное в среднем, чем мой метод? Один из методов, который, казалось бы, сработал, состоял в том, чтобы создать стопку для каждой буквы (26 стопок, в худшем случае), но это занимает столько места, что это невозможно для одного стола.

Answer 1

Это отличный вопрос!Мы провели небольшой эксперимент, чтобы приблизиться к ответу.

Наша установка состояла из

• 3 сортировщиков (A, B и C).

• 3 стека из 40 наборов задач ученика (по одному на каждый сортировщик).Число листов в наборе задач варьировалось от 1 до 5. Листы были сшиты и на верхней части первой страницы были написаны имена учеников.

• 3 алгоритма сортировки для сортировки стопокв алфавитном порядке:

  • Вставка : Возьмите верхний элемент из несортированной стопки и вставьте ее в правильную позицию в отсортированной стопке.Разбрасывание отсортированной стопки разрешено.
  • Ведро : сортируйте каждый предмет по одному из пяти ведер (AE, FJ, KO, PT, UZ).Затем сортируйте каждое ведро, используя сортировку вставками.Объедините отсортированные ведра.
  • Слияние : Разделите предметы на 10 стопок.Сортируйте каждую стопку, используя сортировку вставками.Положите 10 отсортированных стопок в 5 пар.Объедините каждую пару, неоднократно просматривая верхние элементы пары и помещая алфавитно более высокий в нижнюю часть результирующей стопки пары.После объединения 10 стопок в 5 объедините 2 из 5 стопок, чтобы осталось 4 стопки.Затем несколько раз объединяйте попарно, пока не останется одна отсортированная куча.

• Измерения:

  • Время до завершения алгоритма сортировки.
  • Количество неуместных предметов (измерено другим сортировщиком).

• Порядок алгоритмов сортировки был рандомизирован.

• КаждыйВ новом раунде наборы проблемных наборов обменивались между сортировщиками и перемешивались в течение нескольких минут.

• Сортировщики A и B каждый делали по 9 раундов, сортировщик C - по 3 раунда.

• Лист с отсечками по алфавиту и ведру был размещен на столе каждого сортировщика.

Вот изображение нашей установки.

И вот результаты.

Два вывода являются немедленными.

1. Относительно сложный алгоритм сортировки слиянием сформирован плохо.Сортировки слиянием занимали на 57–125% больше времени, чем в средних значениях сортировки корзины / вставки сортировщика, без очевидного увеличения точности.

Мы предполагаем, что начальный этап первого деления стека проблемных наборов на 10 стопок можетспособствовать слиянию тусклых результатов сортировки.Будущие исследователи могут обнаружить, что подобные алгоритмы слияния в сочетании с более эффективными процедурами настройки эффективны.

Несмотря на то, что сортировка ведра и вставки работала хорошо, сортировка ведра была на 13-25% быстрее, чем сортировка вставки внутри сортировщиков.Это различие соответствует примерно минуте времени, сэкономленной для каждой сортировки с набором из 40 задач.

Мы предполагаем, что относительная эффективность сортировки по сегментам будет улучшаться по мере того, как число проблемных наборов для сортировки будет превышать 40и эта сортировка вставки будет доминировать для стеков из 30 или меньше, хотя требуется больше тестирования.Не было четких различий в точности между сортировками ведра и вставки.

Наконец, отметим, что у наших подопытных есть важные индивидуальные различия в способности сортировки.Сортировщик B стабильно превосходил сортировщики A и C в среднем на 39 и 101 секунду соответственно.Это говорит о том, что, хотя используемая процедура сортировки важна для скорости сортировки, способность может объяснить, по крайней мере, большую долю различий в отдельных результатах.Изучение того, что делает немцев такими фантастическими сортировщиками, является перспективной областью для будущих исследований.

Answer 2

В моем отделении есть базовый курс, на котором обычно 500-600 студентов пишут экзамен.Из подхода «след и ошибка» кажется, что сортировка выполняется быстрее всего, сначала выполняя сортировку с использованием примерно одного сегмента на букву.Буква S обычно может быть разделена на два сегмента, в то время как буквы в конце алфавита (x, y, z) обычно могут совместно использовать один интервал.Затем мы сортируем внутри каждого сегмента сортировку вставкой и заканчиваем укладкой блоков.

Для небольших классов (до 30) прямая сортировка вставки является жизнеспособной, но время, необходимое для нахождения правильной позиции для вставки, быстро возрастает.из-под контроля, когда куча растет.

Answer 3

Я основал свой алгоритм на предпосылке, что время, которое у меня уходит на то, чтобы определить правильный порядок для двух элементов, не согласовано.Например, мне легко сказать, что A принадлежит перед D, но мне нужно решить, стоит ли Q перед T или наоборот (вообще говоря, чем ближе буквы к концу алфавита и друг к другу, темболее вероятно, что мне придется мысленно повторять алфавит, чтобы быть уверенным).

Учитывая это, я считаю, что это уменьшает утомительное повторение алфавита, если я разделю тесты на алфавитные «куски»:

• Начало (AF ish)
• Раннее среднее (GK ish)
• Позднее среднее (LP ish)
• Конец (QZ ish).Это больше, потому что (а) это сектор, в котором я хуже всего определяю порядок букв и (б) некоторые из этих букв не часто начинаются с фамилий

Естьперекрытие - то есть иногда я чувствую, что Q - поздняя середина, а иногда я чувствую, что это конец.Это отчасти зависит от того, насколько большими в этом месте находятся груды и какие буквы я сортировал в последний раз ... Моя теория заключается в том, что время, сэкономленное благодаря отсутствию написания алфавита в моей голове, больше, чем дополнительное время, потраченное на сортировку позже.на.

Это, насколько я понял, однако.За исключением первоначальной порции, я никогда не смогу решить, что наиболее эффективно ...

Answer 4

• сортировка по первой букве в M стопки
• как только вам понадобится> = M стопки: поместите все элементы с несовпадающими начальными буквами в корзину
• в конце первого прогона: M сваи завершены
• рекурс, используя остатки из груды мусора

Константа M может быть настроеначтобы соответствовать вашей способности совпадать и поставить несколько букв с первого взгляда.(и доступное дисковое пространство)

На практике вам не понадобится более нескольких прогонов при разумных значениях M.(Закон Зипфа / Парето)

Answer 5

Я использую сортировку ведра. Используйте четыре сегмента и снова сортируйте каждый блок с помощью другого набора из 4 блоков, сортируйте каждый суб-сегмент (1/16) методом грубой силы!

Answer 6

Я просматривал некоторые веб-сайты, на которых обсуждались алгоритмы для использования людьми, и один из тех, что я видел, выполнял своего рода вводную сортировку, где вы кладете один из них в кучу, кладя его прямо туда, где он правильный заказ должен быть.

Неэффективность этого, вероятно, будет связана с необходимостью сканировать кучу, чтобы найти местоположение по мере увеличения кучи, поэтому я думаю, что, чтобы приспособиться к этому, вы можете добавить тег или что-то, что будет действовать как указатель для конкретного алфавитного местоположения. Поскольку вы не заботитесь об алфавитном порядке, кроме первой буквы, это, по сути, приведет к тому, что стоимость вставки будет равна O (1)

.

Это всего лишь мысль, которая у меня возникла, когда я об этом думал, так что я сам на самом деле не пробовал ее и не могу сказать, насколько она эффективна при достаточно больших кучах. Но я думаю, что он должен работать довольно хорошо, так как теги предоставят вам мгновенный доступ к месту, которое вы хотите вставить.

Answer 7

Ваш последний абзац - сортировка вставкой.Если 26 стопок два, используйте 24 :).Если 26 стопок слишком много, разбейте алфавит и экзамены на 5 стопок.Затем отсортируйте каждую стопку, и снова у вас будет 5 коробок (одна с 6).

Answer 8

Из описания проблемы я полагаю, что наиболее эффективный метод аналогичен рекомендации Дональда Кнута о том, как сортировать колоду карт по двум категориям:

1. Распределите тесты по 26 сегментам по первым инициалам.
2. Соберите груды в обратном порядке, с кучей Z сверху и грудой A снизу.
3. Распределите тесты (начиная с вершины одной большой стопки, начиная с шага 2) на 26 сегментов по последним инициалам.
4. Соберите стопки в прямом порядке, с кучей A вверху и стопкой Z внизу.

Поздравляем, ваши экзамены теперь отсортированы в соответствии с вашими требованиями. Сортировка может быть сделана за время O (n), обрабатывая каждый тест ровно дважды.

Можно уменьшить количество сегментов на шаге 1, обработав список классов. Граница между сегментами необходима только для разделения первых инициалов, которые имеют один и тот же последний инициал. Например, если список инициалов в классе - AM, BD, LD, RM, CN, BH, вам нужно будет только отделить BD от LD и AM от RM в первом проходе, поэтому сегменты AK и LZ будут достаточными для первый проход Однако для большого класса сокращение числа сегментов будет, вероятно, небольшим и в любом случае не даст большого преимущества, поскольку в любом случае вам придется обрабатывать все 300 тестов на этом этапе. Кроме того, это усложняет ситуацию, требуя, чтобы компьютерная программа обрабатывала класс последним, и делает ситуацию нестабильной, требуя изменения в случае изменения списка классов. Так как на шаге 3 вам все равно понадобится место примерно для 26 стопок, вы также можете отсортировать их на 26 стопок на шаге 1.

Вы можете попросить студентов выполнить шаг 1 самостоятельно, когда они сдадут тесты.

Answer 9

Quicksort, вероятно, не лучше, как его эффективность зависит от выбора поворота. В любом случае, имея всего 300 экзаменов, я бы создал 26 стопок (по одной на каждую букву) и просто сдал один экзамен для всех экзаменов, поместив их в соответствующие стопки