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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

Наша настройка состояла из

3 сортировщика (A, B и C).
3 стека из 40 наборов задач для учащихся (по одному для каждого сортировщика). Количество листов набора проблем варьировалось от 1 до 5. Листы были сшиты и имели имена учеников, написанные в верхней части первой страницы.
3 алгоритма сортировки для сортировки стеков в алфавитном порядке:
- Вставка: возьмите верхний элемент из несортированной кучи и вставьте в правильное положение в сортированной куче. Разделение сортированной кучи разрешено.
- Ковш. Сортируйте каждый элемент в один из пяти ведер (A-E, F-J, K-O, P-T, U-Z). Затем отсортируйте каждое ведро с помощью сортировки вставки. Объедините сортированные ведра.
- Слияние. Разделите элементы на 10 свай. Сортируйте каждую кучу, используя сортировку вставки. Поместите 10 отсортированных свай на 5 пар. Объедините каждую пару, многократно просматривая верхние элементы пары и помещая ее в алфавитном порядке выше на дно пары, в результате чего куча. После слияния 10 свай в 5 слейте 2 из 5 свай, чтобы осталось 4 сваи. Затем, повторно объединяйте парные, пока не останется одна сортированная куча.
Размеры:
- Время до завершения алгоритма сортировки.
- Количество неустановленных элементов (измеренных другим сортировщиком).
Порядок сортировки алгоритмов был рандомизирован.
Каждый новый раунд заданных стеков был обменен между сортировщиками и перетасован в течение нескольких минут.
Сортировщики A и B выполняли 9 раундов, сортировщик C выполнял 3 раунда.
В каждой таблице сортировщика был помещен лист с сортировкой сортировки алфавита и ведра.

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

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

Два вывода немедленно.

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

Учитывая это, я нахожу, что это уменьшает утомительный алфавит, повторяя, если я делю тесты на алфавитные "куски":

Начало (A-F ish)
Ранний средний (G-K ish)
Поздний средний (L-P ish)
Конец (Q-Z ish). Это больше, потому что (а) это сектор, где я хуже всего решаю порядок букв и (б) некоторые из этих букв не часто начинаются с фамилий

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

Тем не менее, насколько я понял. Помимо начального chunking, я никогда не могу решить, что наиболее эффективно...

Ответ 7

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

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

Ответ 8

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