|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
от 1001 до 2000 и т. д. до 27-го прохода, сортирующего числа от 26 001 до 27 000. Для сортировки в ОЗУ достаточно эффективна программа быстрой сортировки QUICKSORT, разработанная Керниганом и Плоджером. Программа состоит примерно из 40 строк на языке Ратфор (мы рассмотрим несколько программ сортировки в гл. 10 и 12). Поэтому вся программа могла бы состоять из 80 операторов языка Фортран. Она обладает также следующим хорошим свойством: нам не требуется больше беспокоиться об использовании промежуточных файлов на диске. К несчастью, за это достоинство нам приходится расплачиваться чтением 27 раз всего входного файла.
Программа сортировки слиянием читает данные из входного файла один раз, сортирует их с помощью рабочих файлов, которые читаются и записываются многократно, и потом один раз записывает выходные данные:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В алгоритме с 27 проходами входной файл читается много раз, выходной файл записывается только один раз, промежуточные файлы не используются.
|
|
|
|
|
|
|
|
|
Многопроходная сортировка
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С моей точки зрения, предпочтительнее слудующая схема, которая сочетает достоинства двух предыдущих: входной файл читается только один раз и не используются промежуточные файлы:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
