Методы сортировки

Основными операциями, выполняемыми над таблицами, являются упорядочение (сортировка) записей и поиск в таблице записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей таблицы в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если таблица целиком помещается в оперативной памяти ЭВМ,то ее упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются :
С - количество операций сравнения пар ключей,
Р - число перестановок элементов ,
S - резерв памяти.

Среднее количество операций сравнения зависит от метода сортировки и при рациональном выборе метода достигает некоторого минимума,зависящего от n - размера таблицы ( размер таблицы - количество содержащихся в ней записей). Методы внутренней сортировки можно разделить на две группы:
- методы, не требующие резерва памяти;
- методы, требующие резерва памяти.

К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений. Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в таблице и их предварительной упорядоченности.
Рассмотрим алгоритмы наиболее рараспространенных методов внутренней сортировки ( упорядочение выполняется по возрастанию значений ключа ).