Программы •Железо • Драйверы • Хостинг •Энциклопедия рекламы

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

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

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

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