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