Сортировка массивов. Усовершенствованные методы: сортировка Шелла, пирамидальная сортировка, быстрая сортировка

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки – ускорить последующий поиск элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах.

Методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ (для этой памяти характерен быстрый произвольный доступ), а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающем устройстве с механическим передвижением (дисках, лентах).

Основные критерии эффективности алгоритмов сортировки:

- быстродействие;

- экономия памяти;

- сокращение времени, затрачиваемого программистом, на реализацию алгоритма.

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

Для определения эффективности алгоритма будем оценивать числа С – необходимых сравнений ключей и М – присваиваний элементов. Эти числа определяются некоторыми формулами от числа n сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка сравнений.

Сортировка массивов

Введем некоторую терминологию: нам даны элементы – a₁, a₂, …, a_n. Сортировка означает перестановку этих элементов в таком порядке: a_k1, a_k2, …, a_kn, что при заданной функции упорядочения f справедливо отношение f(a_k1)<=f(a_k2)<=…<=f(a_kn).

Обычно функция упорядочения не вычисляется по какому-нибудь правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называют ключом элемента. Для представления элемента a_i будем использовать запись:

type item = record

key: integer;

{описание других компонент}

end;

Прочие компоненты – это все существенные данные об элементе, поле key служит лишь для идентификации элементов. Однако, когда мы говорим об алгоритмах сортировки, ключ – единственная существенная компонента, и нет необходимости выделять все остальные.

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

Сортировка Шелла

Некоторое усовершенствование сортировки простыми вставками было предложено Д.Л. Шеллом в 1959 г. Этот метод продемонстрируем на примере из восьми элементов (рис. 7).

Рисунок 7 - Сортировка Шелла

На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции (4-сортировкой). В примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново (2-сортировкой). На третьем проходе все элементы сортируются обычной сортировкой (1-сортировкой).

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

Этот метод в результате дает упорядоченный массив, а каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки.

Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через с условиями .

Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется барьер.

Каждая h-сортировка требует собственного барьера и что программа должна определять его место как можно проще. Поэтому массив a нужно дополнить не одной компонентой а [0], a компонентами, так что теперь он описывается как

а: array [- .. n] of item; Этот вид сортировки пригоден для последовательностей, имеющих примерно до 70 тыс. элементов.