почему сортировка слиянием предпочтительнее быстрой сортировки для сортировки связанных списков
Я прочитал в форуме следующее:
сортировка слиянием очень эффективна для неизменяемые структуры данных, такие как связанные списки
и
быстрая сортировка обычно быстрее, чем сортировка слиянием, когда данные хранятся в память. Однако, когда набор данных огромный и хранится на внешних устройствах например, жесткий диск, сортировка слиянием явный победитель в плане скорости. Оно минимизирует дорогие чтения внешний драйв
и
при работе со связанными списками сортировка слиянием требует только небольшого постоянного объема вспомогательного хранилища
может кто-нибудь помочь мне понять приведенный выше аргумент? почему сортировка слиянием предпочтительна для сортировки огромных связанных списков? и как это минимизирует дорогостоящие чтения на внешний диск? в основном я хочу понять, почему для сортировки большого связанного списка нужно выбрать сортировку слиянием.
3 ответа:
быстрая сортировка хорошо работает для сортировки на месте. В частности, большинство операций можно определить в терминах замены пар элементов в массиве. Однако для этого вы обычно "проходите" через массив с двумя указателями (или индексами и т. д.) Начинается в начале массива, а другой в конце. Оба затем работают свой путь к середине (и вы сделали с определенным шагом раздела, когда они встречаются). Это дорого с файлами, потому что файлы ориентированы в первую очередь к чтению в одном направлении, от начала до конца. Начиная с конца и стремясь назад, как правило, относительно дорого.
по крайней мере, в своем простейшем воплощении сортировка слияния в значительной степени противоположна. Простой способ его реализации требует только просмотра данных в одном направлении,но включает в себя разбиение данных на две отдельные части, сортировку частей, а затем объединение их вместе.
с помощью связанного списка, это легко взять (например) чередование элементов в одном связанном списке и управление ссылками для создания двух связанных списков из тех же элементов вместо этого. С массивом перестановка элементов таким образом, чтобы чередующиеся элементы переходили в отдельные массивы, легко, если вы хотите создать копию размером с исходные данные, но в остальном более нетривиальную.
аналогично, слияние с массивами легко, если вы объединяете элементы из исходных массивов в новый массив с данными по порядку - но чтобы сделать это в место без создания совершенно новой копии данных-это совсем другая история. В связанном списке объединение элементов из двух исходных списков в один целевой список является тривиальным - опять же, вы просто манипулируете ссылками, не копируя элементы.
Что касается использования Quicksort для создания отсортированных запусков для внешней сортировки слиянием, это действительно работает, но это (решительно) неоптимально, как правило. Чтобы оптимизировать сортировку слиянием, вы обычно хотите максимизировать длину каждого отсортированного "запуска", как вы производить его. Если вы просто читаете данные, которые поместятся в памяти, быстро сортируете их и записываете, каждый запуск будет ограничен (немного меньше) размером доступной памяти.
вы можете сделать совсем немного лучше, чем это, как правило, хотя. Вы начинаете с чтения в блоке данных, но вместо того, чтобы использовать Quicksort на нем, вы строите кучу. Затем, когда вы записываете каждый элемент из кучи в сортированный файл "run", Вы читаете другое элемент из входного файла. Если он больше, чем элемент, который вы только что записали на диск, вставьте его в существующую кучу и повторите.
элементы, которые меньше (т. е. принадлежат до элементов, которые уже были написаны), вы сохраняете отдельно и строите во вторую кучу. Когда (и только когда) ваша первая куча пуста, а вторая куча заняла всю память, вы прекращаете запись элементов в существующий файл "run" и начинаете с нового.
точно, насколько эффективно это будет зависит от первоначальный порядок данных. В худшем случае (входные данные отсортированы в обратном порядке)это не приносит никакой пользы. В лучшем случае (вход уже отсортирован) он позволяет "сортировать" данные за один проход через вход. В среднем случае (ввод в случайном порядке) он позволяет примерно удвоить длину каждого отсортированного прогона, что обычно улучшает скорость на вокруг 20-25% (хотя процент варьируется в зависимости от того, насколько больше ваши данные, чем доступная память).
Quicksort зависит от возможности индексирования в массив или аналогичную структуру. Когда это возможно, трудно победить Quicksort.
но вы не можете индексировать непосредственно в связанный список очень быстро. То есть, если
myList- Это связанный список, тогдаmyList[x], если бы можно было написать такой синтаксис, то пришлось бы начинать во главе списка и следовать за первымxссылки. Это должно быть сделано дважды для каждого сравнения, которое делает Quicksort, и это получит дорого очень быстро.то же самое на диске: Quicksort придется искать и читать каждый элемент, который он хочет сравнить.
сортировка слиянием быстрее в этих ситуациях, потому что она читает элементы последовательно, обычно делая log2(N) передает данные. Там гораздо меньше ввода-вывода участвует, и гораздо меньше времени тратится на следующие ссылки в связанном списке.
Quicksort быстро, когда данные помещаются в память и могут быть адресованы непосредственно. Сортировка слиянием работает быстрее, когда данные не будет вписываться в память или когда это дорого, чтобы добраться до элемента.
обратите внимание, что большие сортировка файлов обычно загружают столько, сколько они могут файла в память, Quicksort, что и записать его во временный файл, и повторять, пока он не прошел через весь файл. В этот момент существует некоторое количество блоков, каждый из которых сортируется, а затем программа выполняет N-образное слияние для получения отсортированного вывода.
в быстрая сортировка будет двигаться записей в середине списка. Чтобы переместить элемент в индекс X, он должен начинаться с 0 и повторять по одной записи за раз.
a mergesort разбивает список на несколько небольших списков и сравнивает только элементы, возглавляющие списки.
настройка для сортировки слиянием обычно стоит дороже, чем итерация, требуемая quicksort. Однако, когда список достаточно велик, или чтение дорого (например, с диска), то время, необходимое для итерации quicksort, становится основным фактором.