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