Почему сортировка сортировки предпочтительна по сравнению со списком быстрого сортировки для сортировки связанных списков

Я прочитал следующее на форуме:

Сортировка слияния очень эффективна для неизменяемые структуры данных, подобные связанным списки

Быстрая сортировка обычно быстрее, чем Объединить сортировку, когда данные хранятся в Память. Однако, когда набор данных огромный и хранится на внешних устройствах таких как жесткий диск, сортировка слияния явный победитель с точки зрения скорости. Это минимизирует дорогостоящие внешний накопитель

при работе со связанными списками, для сортировки слиянием требуется только небольшой постоянный объем дополнительного хранилища

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

Ответ 1

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

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

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

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

Что касается использования Quicksort для создания отсортированных прогонов для внешнего сортирования слияния, он действительно работает, но он (явно) субоптимальный, как правило. Чтобы оптимизировать сортировку слияния, вы обычно хотите максимизировать длину каждого отсортированного "запуска" по мере его создания. Если вы просто читаете данные, которые будут вписываться в память, Quicksort и записывайте их, каждый пробег будет ограничен (немного меньше) размером доступной памяти.

Вы можете сделать немного лучше, чем это, как правило, хотя. Вы начинаете с чтения в блоке данных, но вместо того, чтобы использовать QuickSort, вы создаете кучу. Затем, когда вы пишете каждый элемент из кучи в отсортированный файл "run", вы читаете другой элемент из вашего входного файла. Если он больше, чем элемент, который вы только что записали на диск, вы вставляете его в свою существующую кучу и повторяете.

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

Насколько эффективно это будет зависеть от начального порядка данных. В худшем случае (вход отсортирован в обратном порядке) он не делает ничего хорошего. В лучшем случае (вход уже отсортирован) он позволяет вам "сортировать" данные за один проход через вход. В среднем случае (ввод в случайном порядке) он позволяет приблизительно удвоить длину каждого сортированного прогона, который обычно улучшает скорость примерно на 20-25% (хотя процент варьируется в зависимости от того, насколько больше ваших данных, чем доступная память).

Ответ 2

Quicksort зависит от возможности индексирования в массив или аналогичную структуру. Когда это возможно, трудно победить Quicksort.

Но вы не можете индексировать напрямую в связанный список очень быстро. То есть, если myList является связанным списком, то myList[x], можно ли написать такой синтаксис, будет включать запуск в начале списка и последующие первые ссылки x. Это нужно сделать дважды для каждого сравнения, которое делает Quicksort, и это будет очень дорого.

То же самое на диске: Quicksort придется искать и читать каждый элемент, который он хочет сравнить.

Сортировка сортировки выполняется быстрее в этих ситуациях, поскольку она считывает элементы последовательно, как правило, делает log2 (N) передачей данных. В I/O задействовано гораздо меньше, и гораздо меньше времени тратится на ссылки в связанном списке.

Быстрая сортировка выполняется быстро, когда данные вписываются в память и могут быть устранены напрямую. Mergesort быстрее, когда данные не будут вписываться в память или когда это будет дорого для элемента.

Обратите внимание, что большие сортировки файлов обычно загружают столько, сколько они могут, из файла в память, Quicksort и записывают его во временный файл и повторяют до тех пор, пока не пройдут весь файл. В этот момент есть некоторое количество блоков, каждый из которых сортируется, а затем программа выполняет слияние N-way для создания отсортированного вывода.

Ответ 3

Быстрая сортировка переместит записи в середину списка. Чтобы переместить элемент в индекс X, он должен начинаться с 0 и повторять одну запись за раз.

Слияние объединяет список в несколько небольших списков и только когда-либо сравнивает элементы заголовков списков.

Настройка для сортировки слияния обычно движется дорого, чем итерация, требуемая быстрой сортировкой. Однако, когда список достаточно велик или чтение является дорогостоящим (например, с диска), время, необходимое для итерации quicksort, становится основным фактором.