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