Так можно сделать, отобразив все целые числа из входного файла примерно в 1000 слов, имеющихся в нашем распоряжении в ОЗУ. Таким образом, задача сводится к тому, сможем ли мы представить 27 000 различных целых чисел с помощью примерно 16 000 доступных нам битов? Задумайтесь о таком представлении.
1.4. НАБРОСОК РЕШЕНИЯ
При таком подходе кажется разумным использовать побитовое представление набора данных. Мы представим файл строкой из 27 000 битов, в которой бит I равен 1 в том и только в том случае, когда в файле есть целое число I. (Мой собеседник нашел 11 000 свободных битов; в задаче 1 исследуется случай, когда 16 000 битов - верхний предел.) Такое представление использует три особенности этой задачи, обычно не встречающиеся в задачах сортировки: небольшой диапазон допустимых входных чисел, отсутствие дубликатов, а также то , что с каждой записью не связано никаких других данных, кроме единственного целого числа.
Задавшись побитовой структурой данных для представления множества целых чисел в файле, программу можно написать в виде трех очевидных частей. В первой части подготавливается массив битов - все биты устанавливаются в 0. Вторая часть заполняет этот массив посредством чтения каждого числа из файла и установки соответствующего бита в 1. В третьей части порождается отсортированный выходной файл. Для этого проверяется каждый бит и выводится соответствующее число, если бит равен 1. Пусть N - общее число битов (в нашем случае N = 27 000), тогда программа на псевдоязыке может быть записана так:
Л Часть I: начальное обнуление пассива I/ for I := 1 to N do ВШИ := 0 /ft Часть II: ввести имевшиеся элементы в ыассив #/ для каждого целого числа I из входного файла BitCID := 1 /ft Часть III: выдать упорядоченный файл ft/ for I := i to X do If ВШП = 1 then
записать I в выходной файл
