При работе ЭВМ большую роль играет процесс выбора нужной информации из имеющихся данных. Если данные хранятся не в упорядоченном виде, время, затрачиваемое на поиск данных оказывается очень большим. Чтобы найти нужную запись из N записей, в среднем нужно перебрать N/2 записей (и это при условии, что любая запись найдется, иначе требуется больше попыток). Если же записи упорядочены, то при простейшем алгоритме двоичного поиска требуется lg2(N) попыток. Если в базе находится 10000 записей, поиск в первом случае потребует в среднем 5000 попыток, а во втором – не более 14 попыток. Именно по этой причине, все данные в ЭВМ должны храниться в упорядоченном виде.
Для упорядочивания данных используются программы сортировок.
Сортировка - это расстановка некоторых записей в порядке возрастания или убывания некоторого числового признака - ключа.
Запись - элементарный объект упорядочивания, может быть просто числом или составным типом - символьной строкой, документом сложной структуры и т.д. Каждая запись обладает некоторым признаком, в соответствии с которым ее можно сравнивать с другими на предмет их очередности (порядка). Такой признак называется ключем. Для ключей определено соотношение порядка, т.е. их можно сравнивать на "больше", "меньше" и "равно".
Пересортировать записи - означает расставить их так, чтобы ключи записей изменялись монотонно (или не убывали – сортировка по возрастанию, или не возрастали - сортировка по убыванию).
Понятие качества алгоритма сортировки.
Чем больше количество записей (N), тем больше действий (сравнений и переписываний) нужно сделать, чтобы упорядочить набор. При этом если при увеличении N в два раза число действий увеличивается в 8 раз, длительность алгоритма считается пропорциональной N3, если увеличивается в 4 раза - пропорциональной N2 и т.д. Чем меньше длительность, тем лучше алгоритм. Обычно алгоритмы сортировок пропорциональны N2, лучшие - пропорциональны N*ln(N). Универсального наилучшего алгоритма не существует: для разных наборов данных наискорейшими будут различные алгоритмы.
Сортировки бывают двух типов: внутренняя сортировка и внешняя сортировка.
1. Если весь исходный набор записей помещается в оперативную память и процесс сортировки выполняется без использования внешней памяти для промежуточных результатов, сортировка называется внутренней.
2. Если упорядочивание производится с созданием промежуточных наборов данных на внешней памяти с последующим чтением их для завершения сортировки, она называется внешней.
Основные методы сортировок.
Выделяется 5 основных методов сортировки, из них различными модификациями получено множество (несколько десятков) рабочих алгоритмов сортировок. Эти методы (их суть описана ниже) называются: 1 - вставками; 2 - обменом; 3 - выбором; 4 - пересчетом; 5 - слиянием. Первые 4 метода - внутренние сортировки, последний - внешняя сортировка.
Объекты сортировки.
Каждая запись набора данных обладает ключом. Иногда ключ определяется просто - например, если запись - это просто число, то ключ совпадает с самой записью. Если необходимо упорядочить некоторые документы (например, анкеты людей) по содержанию внутреннего числового поля (например, года рождения) то ключ также легко выбирается из записи. Но если надо расставить по алфавиту множество слов, то ключ для каждого слова определяется достаточно сложно и долго. Иногда бывает выгодно сначала один раз вычислить и записать ключ каждой записи и исходный набор данных представить в виде:
┌──────────┬──────────┬───────────┐
│адр.1 зап.│ключ1 зап.│запись N 1 │
└──────────┴──────────┴───────────┘
┌──────────┬──────────┬───────────┐
│адр.2 зап.│ключ2 зап.│запись N 2 │
└──────────┴──────────┴───────────┘
. . . .
┌──────────┬──────────┬───────────┐
│адр.n зап.│ключn зап.│запись N n │
└──────────┴──────────┴───────────┘
В зависимости от соотношения размеров записей и ключей выбирают разные виды сортировок.
1. Если записи маленькие (числовые), упорядочивают сами записи. Это - сортировка записей.
2. Если записи большие по размерам (например, документы), а ключи - маленькие, составляют таблицу из ключей с адресами записей:
┌──────────┬──────────┐
│адр.1 зап.│ключ1 зап.│
└──────────┴──────────┘
┌──────────┬──────────┐
│адр.2 зап.│ключ2 зап │
└──────────┴──────────┘
. . . .
┌──────────┬──────────┐
│адр.n зап.│кл. n зап.│
└──────────┴──────────┘
Затем сортируют эту таблицу, и переписывают записи в соответствии с порядком расставленных ключей, используя хранящиеся в таблице адреса каждой из исходных записей. Это - сортировка ключей.
3. Если и записи и ключи большие по занимаемому месту, их переписывание при сортировке очень невыгодно. Составляется таблица из одних адресов записей (по каждому адресу можно найти не только запись, но и ее ключ):
┌──────────┐
│адр.1 зап.│
└──────────┘
┌──────────┐
│адр.2 зап.│
└──────────┘
. . . .
┌──────────┐
│адр.n зап.│
└──────────┘
эта таблица сортируется в соответствии с ключами, которые находятся по этим адресам и записи затем переписываются один раз в соответствии с порядком переставленных адресов. Это - сортировка адресов.
