Сортировка выбора выбора v. Сортировка выбора
Я провел некоторое исследование по сортировке выбора замены, и я не могу найти ни одной реализации этого или хорошей, тщательной реализации сортировки выбора замены! Может быть, я не выгляжу достаточно усердно, но Google путает выбор замены с сортировкой выбора... так что меня это удивляет:
Каковы реальные различия между сортировкой выбора и заменой выбора?
Где я могу найти реализацию замены выбора сортировки (или руководство по ее написанию)?
Какие характеристики сортировки с заменой выбора делают ее более желательной, чем другие алгоритмы сортировки?
Известен ли этот алгоритм под другими именами?
2 ответа
Я не видел этот алгоритм, описанный более подробно ранее, и я основываю свой анализ на том, что я собрал, прочитав этот набор примечаний к лекции.
Насколько я понимаю, ключевое отличие между сортировкой выбора и сортировкой выбора замены заключается в том, что сортировка выбора предназначена для сортировки полной последовательности, хранящейся в основной памяти, в то время как сортировка выбора замены предназначена для преобразования несортированной последовательности, слишком большой для размещения в основной памяти, в серия "цепочек" отсортированных последовательностей, которые могут храниться во внешней памяти. Эти внешние нити могут затем быть объединены вместе, чтобы сформировать общую отсортированную последовательность. Несмотря на сходство их имени и одного или двух ключевых этапов работы алгоритма, они предназначены для решения принципиально разных задач.
Выбор сортировки
Есть много хороших учебных пособий по сортировке выбора, доступных в Интернете, поэтому я не буду тратить слишком много времени на их обсуждение. Интуитивно, алгоритм работает следующим образом:
- Найдите наименьший элемент и поменяйте его местами в позиции 0 массива.
- Найдите второй наименьший элемент и поменяйте его местами в позиции 1 массива.
- Найдите третий самый маленький элемент и поменяйте его местами в позиции 2 массива
- ...
- Найдите n-й наименьший элемент и поменяйте его местами в позиции n - 1 массива.
Это предполагает, что массив может храниться полностью в памяти, и в этом случае этот алгоритм выполняется за время Θ (n2). Это не очень быстро, и для больших наборов данных не рекомендуется.
Выбор замены Сортировка
Этот алгоритм был описан в 1965 году Дональдом Кнутом, поэтому он предназначен для работы в совершенно иной вычислительной среде, чем та, к которой мы привыкли. Компьютеры имеют очень мало памяти (как правило, фиксированное количество регистров), но имеют доступ к большим внешним дискам. Обычно строят алгоритмы, которые загружают некоторые значения в регистры, обрабатывают их там, а затем сбрасывают прямо обратно во внешнее хранилище. (Интересно, что это похоже на то, как работают процессоры прямо сейчас, за исключением основной памяти вместо внешнего хранилища).
Давайте предположим, что у нас достаточно места в памяти для хранения двух массивов: первый массив Values размером n, который может содержать кучу значений и второй массив Active размера n, который содержит логические значения. Мы попытаемся взять большой входной поток несортированных значений и приложим все усилия, чтобы отсортировать их, учитывая, что у нас достаточно места в памяти для хранения Active а также Values массивы, плюс несколько дополнительных переменных для места хранения.
Идея алгоритма заключается в следующем. Сначала загрузите n значения из внешнего источника, содержащие несортированную последовательность непосредственно в Values массив. Затем установите все Active значения для true, Например, если n = 4мы могли бы иметь эту настройку:
Values: 4 1 0 3
Active: Yes Yes Yes Yes
Алгоритм сортировки выбора замены работает путем многократного поиска наименьшего значения в Values массив и запись его в выходной поток. В этом случае мы начнем с поиска значения 0 и записи его в поток. Это дает
Values: 4 1 3
Active: Yes Yes Yes Yes
Output: 0
Теперь у нас есть пустое место в нашем Values массив, так что мы можем получить другое значение из внешнего источника. Давайте предположим, что мы получаем 2. В этом случае у нас есть эта настройка:
Values: 4 1 2 3
Active: Yes Yes Yes Yes
Output: 0
Обратите внимание, что поскольку 2 > 0 и 0 были наименьшим элементом, мы гарантируем, что когда мы записали 0 в вывод, 2 не должно было предшествовать ему. Это хорошо. Поэтому мы переходим к следующему шагу алгоритма и снова находим здесь наименьший элемент. Это 1, поэтому мы отправляем его на устройство вывода:
Values: 4 2 3
Active: Yes Yes Yes Yes
Output: 0 1
Теперь прочитайте другое значение из внешнего источника:
Values: 4 -1 2 3
Active: Yes Yes Yes Yes
Output: 0 1
Теперь у нас проблемы. Это новое значение (-1) ниже, чем 1, что означает, что если мы действительно хотим, чтобы это значение входило в вывод в отсортированном порядке, оно должно предшествовать 1. Однако у нас недостаточно памяти, чтобы перечитать с Устройство вывода и исправить его. Вместо этого мы собираемся сделать следующее. А пока давайте сохраним -1 в памяти. Мы сделаем все возможное, чтобы отсортировать оставшиеся элементы, но когда мы закончим, мы выполним вторую итерацию генерации отсортированной последовательности и поместим -1 в эту последовательность. Другими словами, вместо того, чтобы производить одну отсортированную последовательность, мы собираемся создать две.
Чтобы указать в памяти, что мы еще не хотим выписывать -1, мы отметим слот с -1 как неактивный. Это показано здесь:
Values: 4 -1 2 3
Active: Yes NO Yes Yes
Output: 0 1
Отныне мы будем просто делать вид, что -1 здесь нет.
Давайте продолжим дальше. Теперь мы находим наименьшее значение в памяти, которое все еще активно (2), и записываем его на устройство:
Values: 4 -1 3
Active: Yes NO Yes Yes
Output: 0 1 2
Теперь мы извлекаем следующее значение из устройства ввода. Давайте предположим, что это 7:
Values: 4 -1 7 3
Active: Yes NO Yes Yes
Output: 0 1 2
Поскольку 7 > 2, он идет после 2 в выводе, поэтому мы ничего не делаем.
На следующей итерации мы находим наименьшее активное значение (3) и записываем его:
Values: 4 -1 7
Active: Yes NO Yes Yes
Output: 0 1 2 3
Мы вытягиваем следующее значение из устройства ввода. Давайте предположим, что это также 3. В этом случае мы знаем, что, поскольку 3 является наименьшим значением, мы можем просто записать его непосредственно в выходной поток, так как 3 является наименьшим из всех значений здесь, и мы можем сохранить себя итерацией:
Values: 4 -1 7
Active: Yes NO Yes Yes
Output: 0 1 2 3 3
Теперь мы извлекаем следующее значение из устройства ввода. Предположим, что это 2. В этом случае, как и раньше, мы знаем, что 2 должно предшествовать 3. Так же, как и ранее -1, это означает, что нам нужно пока удерживать 2 в памяти; мы выпишем это позже. Теперь наша установка выглядит так:
Values: 4 -1 7 2
Active: Yes NO Yes NO
Output: 0 1 2 3 3
Теперь мы находим наименьшее активное значение (4) и записываем его в устройство вывода:
Values: -1 7 2
Active: Yes NO Yes NO
Output: 0 1 2 3 3 4
Предположим, что теперь мы читаем в 1 как наш следующий ввод. Поэтому мы помещаем это в Values, но отметьте это как неактивное:
Values: 1 -1 7 2
Active: NO NO Yes NO
Output: 0 1 2 3 3 4
Есть только одно активное значение, которое равно 7, поэтому мы запишем его:
Values: 1 -1 2
Active: NO NO Yes NO
Output: 0 1 2 3 3 4 7
Давайте предположим, что теперь мы читаем 5. В этом случае, как и раньше, мы сохраняем его, но помечаем слот как неактивный:
Values: 1 -1 5 2
Active: NO NO NO NO
Output: 0 1 2 3 3 4 7
Обратите внимание, что все значения теперь неактивны. Это означает, что мы вычеркнули из памяти все значения, которые могут быть включены в текущий прогон вывода. Теперь нам нужно пойти и выписать все значения, которые мы держали на потом. Для этого мы помечаем все значения как активные, а затем повторяем как раньше:
Values: 1 -1 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7
-1 - наименьшее значение, поэтому мы выводим его:
Values: 1 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1
Предположим, что мы читаем 3. -1 < 3, поэтому мы загружаем его в Values массив.
Values: 1 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1
1 - наименьшее значение здесь, поэтому мы удалим его:
Values: 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1
Давайте предположим, что у нас нет входных значений. Мы отметим этот слот как выполненный:
Values: --- 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1
2 идет дальше:
Values: --- 3 5 ---
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1 2
Тогда 3:
Values: --- --- 5 ---
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1 2 3
Наконец, 5:
Values: --- --- --- ---
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1 2 3 5
И мы сделали! Обратите внимание, что результирующая последовательность не отсортирована, но она намного лучше, чем раньше. Теперь он состоит из двух нитей, которые находятся в отсортированном порядке. Объединение их вместе (так же, как мы выполняли бы слияние для сортировки слиянием), приведет к сортировке полученного массива. Этот алгоритм мог потенциально произвести гораздо больше нитей, но поскольку наш выборочный ввод был небольшим, у нас было только два.
Так как быстро это? Итак, каждая итерация цикла выполняет в общей сложности не более n сравнений (в памяти), одного чтения и одной записи. Таким образом, если в потоке N полных значений, алгоритм выполняет O(nN) сравнений и O(N) операций с памятью. Если операции с памятью дороги, это не так уж и плохо, хотя в конце вам понадобится второй проход, чтобы объединить все воедино.
В псевдокоде алгоритм выглядит так:
Make Values an array of n elements.
Make Active an array of n booleans, all initially true.
Read n values from memory into Values.
Until no values are left to process:
Find the smallest value that is still active.
Write it to the output device.
Read from the input device into the slot where the old element was.
If it was smaller than the old element, mark the old slot inactive.
If all slots are inactive, mark them all active.
Я был бы шокирован, если бы была какая-то причина, чтобы кодировать этот алгоритм сейчас. Это имело смысл много десятилетий назад, когда память была действительно очень маленькой. В настоящее время доступны гораздо лучшие алгоритмы внешней сортировки, и они почти наверняка превзойдут этот алгоритм.
Надеюсь это поможет!
Заменяющая сортировка по-прежнему используется для внешней сортировки, поскольку она будет производить наименьшее количество строк для объединения, а объединение является самой дорогой частью сортировки. Используемый подход немного сложнее, чем предоставленный превосходный пример templatetypedef, но в основном он буферизует множество записей, сортирует их, собирает записи последовательности, такие как -1 1 и т. Д., И удерживает их в буфере, записывает младшую часть последовательности, заполняет пустое пространство, снова сортирует, объединяет из буфера любые записи, которые вписываются, и повторяется до тех пор, пока последовательность не может быть продолжена, затем выдает последовательность, удаляет буферизованные записи последовательности и новые входные записи, начиная со следующей строки. Повторите до конца ввода.
В некоторых приложениях объединение не требуется, поскольку сортировочная замена сметает записи последовательности и затем вставляет их позже в нужное место. Это стало неожиданностью для многих коммерческих клиентов в 1964 году, когда Honeywell и IBM представили этот вид.