Энциклопедия Turbo Pascal. Главы 1-4 - Глава 1. Сортировка и поиск
ОГЛАВЛЕНИЕ
Глава 1. Сортировка и поиск
В информатике, по-видимому, нет более глубоко исследованных задач, чем задачи сортировки и поиска. Подпрограммы сортировки и поиска используются фактически во всех программах, работающих с базами данных, а также в компиляторах, интерпретаторах и в операционных системах. В этой главе рассматриваются основные вопросы сортировки и поиска. Сортировка рассматривается первой, поскольку она обычно делает поиск данных более простым и быстрым.
Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если
i <= i <= ... <= i
Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах. В этой главе рассматривается в основном сортировка первого вида, поскольку она представляет наибольший интерес для пользователей микрокомпьютеров. Однако в конце главы делается общий метод сортировки последовательных файлов.
Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляются полное имя и адрес. Для простоты в примерах, иллюстрирующих методы сортировки, используются символьные массивы. Затем будет показано, как эти методы можно адаптировать к любым структурам данных.