1.1. ДРУЖЕСКИЙ РАЗГОВОР
Моя ошибка была в том, что я ответил на вопрос, вкратце объяснив, как надо выполнять сортировку на диске. Так как мое предложение изучить классическую книгу Кнута "Сортировка и поиск" не было встречено с энтузиазмом - собеседника больше волновало решение конкретной задачи, а не продолжение своего образования, - я рассказал ему о программе сортировки на диске, описанной в гл. 4 книги Кер-нигана и Плоджера "Программные средства". Эта программа состоит из 12 процедур и содержит около 200 строк в кодах языка Ратфор. На ее преобразование в несколько сотен строк на языке Фортран и тестирование потребовалось бы около недели.
Сомнения моего собеседника в том, что я разрешил его проблему, навели меня на правильный путь. В дальнейшем наша беседа протекала так (мои вопросы выделены курсивом):
Зачем вам понадобилось писать программу сортировки? Почему не воспользовались системными средствами сортировки?
Мне необходимо выполнить сортировку в рамках большой системы, а в операционной системе нет возможности для перехода от программы пользователя к системным программам.
Что конкретно вам надо сортировать? Сколько записей в файле, каков формат каждой записи?
Файл содержит до 27 000 записей, каждая запись - это 16-разрядное целое число.
Подождите минутку. Если файл настолько мал, зачем вообще связываться с диском? Почему бы просто не сортировать в ОЗУ?
Хотя машина имеет ОЗУ емкостью 0.5. Мбайта, процедура сортировки - только часть большой программы. Я предполагаю, что в этот момент будет свободно всего около 1000 16-разрядных слов.
Можете ли вы сообщить еще что-нибудь об этих записях?
Каждая из них - это целое число в диапазоне от 1 до 27 000 и ни одно из них не встречается более одного раза.
Постановка задачи выяснилась из контекста. Эта система использовалась для избирательных округов (автоматической перекройки этих округов), а сортировать надо было индексы избирательных участков, образующих избирательный округ. Каждый участок в штате имеет свой уникальный номер в диапазоне от 1 до 27 000 (число участков в самом
