Энциклопедия Turbo Pascal. Главы 1-4 - Глава 1. Сортировка и поиск

ОГЛАВЛЕНИЕ

Глава 1. Сортировка и поиск

В информатике,  по-видимому, нет более глубоко исследованных задач,  чем задачи сортировки и поиска. Подпрограммы сортировки и поиска используются фактически во всех программах,  работающих с базами данных, а также в компиляторах, интерпретаторах и в операционных системах.  В этой главе рассматриваются основные вопросы сортировки и поиска. Сортировка рассматривается первой, поскольку она обычно делает поиск данных более простым и быстрым.

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если

                  i <= i  <= ...  <= i

Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в  виде файла прямого доступа,  и сортировка последовательных файлов,  находящихся на дисках или магнитных лентах. В этой главе рассматривается в основном сортировка первого вида, поскольку она представляет наибольший интерес для пользователей микрокомпьютеров.  Однако в конце главы делается общий метод сортировки последовательных файлов.

Основное отличие между сортировкой массивов и  сортировкой последовательных файлов заключается в том,  что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами.  Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.

В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки,  который используется в сравнениях.  Когда выполняется обмен,  передается вся структура данных.  Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс,  а в  операциях обмена к  почтовому индексу добавляются полное имя и адрес.  Для простоты в примерах,  иллюстрирующих методы сортировки, используются символьные массивы.  Затем будет показано,  как эти методы можно адаптировать к любым структурам данных.