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