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