Сортировка обменом

Классификация алгоритмов сортировки

Постановка задачи сортировки

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ СОРТИРОВКИ ИНФОРМАЦИИ

Литература

Пусть задан некоторый набор данных, состоящий из N записей Х1,

Х2,..., ХN. Каждая запись Хi кроме информации содержит поле ключа

Кi. Требуется расставить записи в наборе данных в таком порядке

XL1, XL2,..., XLN, чтобы для заданной функции сортировки F

было справедливо соотношение

F(XL1) < F(XL2) <...< F(XLN) или K(XL1) < K(XL2) <...< K(XLN).

Таким образом, сортировка (упорядочение) - это процесс

целенаправленной перестановки записей, при котором их взаимное

расположение в наборе данных приводится в порядок, определяемый

некоторым известным ключом. Функция сортировки F задает отношение

порядка. Порядок может быть алфавитный, хронологический, порядок

возрастания или убывания значений ключей и т.д.

В информационных системах некоторый набор данных хранится

в отсортированном виде или для того, чтобы автоматизировать извлечение и вывод информации, или для того, чтобы сделать машинный доступ к данным более эффективным. О важности проблемы сортировки

говорит тот факт, что в информационных системах в среднем более 25 % машинного времени систематически тратится на сортировку.

Представьте, насколько трудно было бы пользоваться словарем, если

бы слова в нем не располагались в алфавитном порядке. Точно также от

порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит

скорость и простота алгоритмов, предназначенных для их обработки.

Сортировка называется устойчивой, если она удовлетворяет

условию, что записи с одинаковыми ключами при сортировке остаются в прежнем порядке, т.е. считается

F(XLi) < F(XLj), если K(XLi)=K(XLj) при i < j.

В настоящее время известно несколько десятков различных

методов сортировки информации. Они различаются сложностью, быстродействием и объемом занимаемой памяти.

1) Все методы сортировки в зависимости от структуры информации

делятся на большие две группы - внутренние и внешние.

Внутренние методы применяются к наборам данных, которые цели-

ком помещаются в основной (оперативной) памяти ЭВМ.

Внешние методы применяются к последовательностям записей,

которые в процессе сортировки должны располагаться на устройствах

внешней памяти (лентах, дисках, барабанах и т.д.).

Методы сортировки бывают сравнительные и распределительные.

2) В сравнительных методах элементы сортируются по относительной

величине ключей записей.

В распределительных методах обследуется каждый ключ символ

за символом. Промежуточное размещение ключа зависит не от относи-

тельной величины ключа, а от характеристики, получаемой при сравнении этого ключа с некоторым стандартом.

Методы сортировки бывают простые и комбинированные.

3) Простая сортировка использует один и тот же метод в течение

всего процесса сортировки.

Комбинированная сортировка предполагает одновременное использование двух или более методов.

4) В зависимости от используемого метода сортировки упорядоченная

последовательность записей или размещается на том же участке памяти,

что и исходная(минимальная по памяти сортировка), или требует

для своего формирования дополнительного участка памяти (не минимальная по памяти сортировка).

5) Кроме того, исходная последовательность может быть задана вся

сразу, либо ее элементы поступают на вход алгоритма по одному.

Как правило, различают следующие алгоритмы сортировки: обмен,

выбор, вставка, слияние (сравнительные) и поразрядная сортировка

(распределительная).

(Предложить отсортировать монеты).

Процесс сортировки записей состоит из просмотров и сравнений

ключей, а также из расположения элементов в соответствии с результатом сравнения. Поэтому критериями оценки эффективности методов

сортировки являются количество операций сравнения пар ключей

записей, число перестановок записей (быстродействие) и дополнительный объем памяти, требуемый для реализации метода сортировки.

При сортировке методом обмена два определенным образом выбранных элемента, расположение которых не соответствует порядку, меняют местами. Этот процесс повторяется до тех пор, пока остаются такие пары. К обменным относятся следующие сортировки: парный обмен, стандартный обмен (метод "пузырька"), шейкер - сортировка, метод Бэтчера, "быстрая сортировка", "челночная" сортировка и др. Все эти методы различаются между собой способами просмотра и выбора в сортируемой последовательности элементов для сравнения.

Примечание. Все примеры будем рассматривать:

1) на массивах,

2) с числовыми ключами и

3) по возрастанию.

Рассмотрим четыре метода: метод стандартного обмена, метод Шелла, метод просеивания, Шейкер-сортировка