Объяснение алгоритма внешней быстрой сортировки

Question

Я пытаюсь понять внешнюю версию быстрой сортировки (когда данные не могут быть помещены в основную память).Я нашел следующую ссылку и аналогичное объяснение в Wiki процедуры внешней быстрой сортировки:

Определение: Считать первый и последний элементы M / 2 в буфер(буфер действует как стержень в быстрой сортировке) и сортирует их.Прочитайте следующий элемент с начала или до конца, чтобы сбалансировать письмо.Если следующий элемент меньше наименьшего из буфера, запишите его в доступное место в начале.Если больше, чем величайший, запишите его до конца.В противном случае запишите наибольшее или наименьшее из буфера и поместите следующий элемент в буфер.Сохраняйте написанные максимальные нижние и минимальные верхние клавиши, чтобы избежать использования средних элементов в порядке.Когда закончите, напишите в буфер.Рекурсивно отсортируйте меньший раздел и выполните цикл для сортировки оставшегося раздела.

У меня проблемы с пониманием:

• Имеет ли M значение размера основной памяти?А у меня на диске осталось N-M элементов?

• The buffer acts like the pivot in quicksort - означает ли это, что мне нужно разделить оставшиеся N-M элементы с диска на две части aи b, где элементы из a ниже, чем все элементы из буфера, а элементы из b больше или равны максимальному элементу из буфера?

• Read the next element from the beginning or end to balance writing.Что значит написание баланса ?Должен ли следующий элемент считываться из буфера (памяти) или с накопителя?

• Otherwise write the greatest or least of the buffer, and put the next element in the buffer - если я помещаю следующий элемент в буфер (который уже отсортирован), мне нужно снова отсортировать буфер?

Некоторый пример того, как это работает, или лучшее объяснение было бы очень полезно.

Answer 1

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

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

Является ли M ссылкой на размер основной памяти?

В зависимости от контекста, размер рабочей области памяти равен M · sizeof (элемент).Требуется дополнительная доступная память для чтения в элементе без перезаписи буфера.

'NM` элементов на некотором диске?

Да, поскольку память может удерживать толькоМ элементов, а затем элементы NM остаются на внешнем устройстве.

Буфер действует как стержень в быстрой сортировке?

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

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

Есть место для записи M / 2 элементов в начале или конце файла.Первый прочитанный элемент может быть прочитан с любого конца.Если элемент читается с начала + M / 2.затем наименьший элемент в буфере записывается в начале, все еще оставляя пространство M / 2 для элементов, которые будут записаны.Если элемент читается с конца - M / 2, то самый последний элемент записывается в последний элемент в файле, оставляя место M / 2 в конце для элементов, которые должны быть записаны.

Проблема салгоритм на данный момент.Поскольку каждый элемент читается, его необходимо объединить в буфер из M элементов, что очень медленно.Одним из решений этой проблемы было бы использование кучи min-max для буфера.

https://en.wikipedia.org/wiki/Min-max_heap

В конце концов файл записывается, начиная с обоих концов, встречаясь в средних элементах M, гдебуфер элемента M затем записывается.На этом этапе все элементы на начальной стороне файла меньше или равны всем элементам на конечной стороне файла, и файл можно рассматривать как 2 раздела.Затем каждый раздел разбивается на разделы, в результате чего получается 4 раздела, затем 8 разделов и т. Д., Пока в конечном итоге раздел не помещается в память и не используется нормальная сортировка памяти.и пишет один элемент за раз.Было бы намного быстрее зарезервировать часть памяти для буферизации чтения и записи в группах.