Стр. 74 - Основы алгоритмов и структур данных

72 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5. МЕТОДЫ СОРТИРОВКИ
Под сортировкой обычно понимают процесс перестановки объектов
данного множества в определенном порядке. Цель сортировки — облегчить
последующий поиск элементов в отсортированном множестве. В этом смысле
элементы сортировки присутствуют почти во всех задачах. Упорядоченные
объекты содержатся в телефонных книгах, в ведомостях подоходных налогов, в
оглавлениях, в библиотеках, в словарях, на складах, да и почти всюду, где их
нужно разыскивать.
Для простоты рассуждений предполагаем, что таблица не содержит двух
одинаковых ключей, т.е. если j i ≠ , то либо j i x x < , либо j i x x > . Будем
считать, что запись в таблице состоит из одного ключа, и в качестве ключей
используются целые числа, расположенные в неизвестном нам порядке.
Очевидно, основные расходы при сортировке приходятся на 2 операции:
1) сравнение ключей.
2) перемещение ключей.
Элементарными операциями будем считать:
1) взаимную перестановку двух элементов j i x x ↔ , то есть
1 2 6 4 5 3
1 2 3 4 5 6
2) изъятие одного элемента со своего места и вставка его непосредственно
справа или слева от какого-либо другого элемента. Эту операцию удобно
применять, например, при использовании связных списков.
Выбор из двух способов перемещения зависит от структуры данных и
алгоритма сортировки.