Сортировка больших, двоичных, фиксированных записей длины с QSORT

Question

Я хотел бы отсортировать большой файл с 20 байтами (это не структура) двоичных записей с помощью QSORT.

В файле содержится 800 000 000 записей.

У меня 2 вопроса:

• , что является лучшим способом для сортировки данных в 20 байт в зависимости от сравнения QSort?

INT сравнения (константный вакуум * а, сопзЬ пустота * б)

• и просто, как сделать вид с 800 000 000 записей? Я не могу записать все это в память.

Спасибо.

Answer 1

Как отмечалось многими комментаторами, это выглядит как отличная работа для external sorting algorithm, алгоритма сортировки, который предназначен для случая, когда вы не можете подобрать все объекты для сортировки в памяти за один раз. Для этой настройки могут быть адаптированы многие алгоритмы сортировки, такие как quicksort, сортировка ведра и mergesort. Если вы хотите относительно простой вариант, подумайте об использовании внешнего слияния k-way: разделите данные на несколько диапазонов, чтобы каждый диапазон вписывался в память, сортировал каждый диапазон в памяти и записывал результаты обратно на диск. Затем сделайте слияние k-way на этих диапазонах: откройте каждый файл для чтения, одновременно прочитайте один большой блок каждого файла и используйте обычную операцию слияния k-way на этих блоках. Каждый раз, когда вы исчерпываете все элементы в блоке, просто читайте другой блок из файла.