8.1. Сортировка. Основные понятия

Пусть задан -файл, состоящий из записей . Припишем каждой записи ключ . Ключ – какое-либо отдельное поле или комбинация полей записи. Часто запись целиком составляет поле ключа. Будем считать, что на множестве ключей задано отношение линейного порядка или следования с обычными свойствами, т.е. элементы этого множества можно выстроить в порядке не убывания (не возрастания). Задача сортировки файла ставится так.

Найти такую перестановку записей -файла, чтобы в -файле для записей их ключи располагались в неубывающем порядке: .

Для получения -файла из -файла в общем случае требуется физическое перемещение записей в памяти компьютера. Однако во многих случаях реальная перестановка не требуется. Достаточно описать ее некоторым способом так, чтобы обеспечить непосредственный доступ к записям в соответствии следованию их ключей. Сделать это можно посредством адресного кодирования или адресной перестановки, в которой сортируются индексы (адреса) элементов-записей, а не сами записи. Правда в этом случае под адреса требуется дополнительная память. Часто адресное кодирование применяется в качестве первого этапа для обычной сортировки.

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

Пример 2. Отсортировать числовой массив: 7,2 3 8 4 8 5,14 9 1.

О

Адресная сортировка: 7,2 3 8 4 8 5,14 9 1

5 2 6 3 7 4 8 1