Как отсортировать n ^ 2 элементов в 2n RAM

Question

Может кто-нибудь сказать, пожалуйста, как отсортировать n ^ 2 элементов, используя 2n объема оперативной памяти. Одним из возможных подходов является разделение на n массивов размером n каждый. Затем выполните сортировку слиянием в n элементах и, наконец, сохраните размер n в куче n массивов. Однако это будет означать, что каждый раз, когда размещается один элемент, я выполняю чтение с диска, а каждый раз, когда n элементов завершается, я записываю на диск. Есть лучшие предложения? Спасибо.

Answer 1

Если у вас есть реализация очереди приоритетов, не обращающая внимания на кэш, вы можете использовать ее для достижения оптимального времени работы с точки зрения передачи памяти на каждом уровне в иерархии дисков и памяти (см. http://courses.csail.mit.edu/6.897/spring05/lec/lec23.pdf).

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

Answer 2

Это невозможно.Вам нужно n ^ 2 памяти для отдельных элементов.

Если вы не учитываете это очевидное потребление памяти, я рекомендую один из алгоритмов сортировки на месте, например, heapsort.Это займет O (1) дополнительного пространства.

Если вы ищете алгоритм внешней сортировки, в котором внешнее хранилище не учитывается, а только внутреннее, я рекомендую использовать восходящую сортировку слиянием.Вы можете заставить это потреблять столько или меньше внутренней памяти, сколько вы хотите;чтобы использовать приблизительно 2n памяти, всегда считывайте n / 2 элемента из каждого частично отсортированного набора и объединяйте их в другой массив из n элементов;затем запишите результат обратно на диск (желательно в отдельный файл).