2.2. Алгоритм сортировки вставками

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

Программа реализации алгоритма сортировки приведена ниже в Лабораторной работе 3.

2.3. Алгоритм сортировки выбором элемента

Сортировка выбором элемента - это наиболее привычный и в то же время не самый худший способ решения задачи. В массиве нужно найти элемент с минимальным значением и поменять его местами с первым элементом массива (для сортировки по убыванию - это нужно сделать с максимальным элементом!). После этого элемент с минимальным значением отыскивается среди всех элементов, кроме первого, и меняется значениями со вторым элементом массива и т.д. В результате все элементы выстраиваются по порядку.

Программа реализации алгоритма сортировки приведена ниже в Лабораторной работе 3.

2.4. Алгоритм быстрой сортировки (метод Хоора)

Метод “быстрой” сортировки, предложенный К.Хоором, основан на разделении массива на два непустых непересекающихся подмножества элементов. При этом в одной части массива должны оказаться все элементы, которые не превосходят по значению некоторый предварительно выбранный элемент массива, а в другой части - все элементы, не меньшие его. Аналогично следует поступить с каждой из полученных групп (при этом элемент для разделения можно выбирать просто из “середины” группы). Очевидно, что на определенном этапе массив окажется полностью отсортированным.

В подавляющем большинстве реальных случаев использование “быстрой” сортировки дает лучшие результаты по времени, чем все прочие методы. Однако следует иметь в виду, что для нее нет гарантированной низкой трудоемкости. Более того, иногда трудоемкость достигает значительной величины и не может быть снижена. Исходя из этого, в особо критических ситуациях, когда результат должен выдаваться за жестко лимитированное время, применять “быструю” сортировку следует очень осмотрительно. Создатель языка Паскаль Н.Вирт сказал по поводу этого алгоритма следующее: “быстрая сортировка напоминает азартную игру, где следует заранее рассчитать, сколько можно позволить себе проиграть в случае невезения”.

2.5. Алгоритм пирамиды (метод Уильямса-Флойда)

Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма “пирамиды”. Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого “пирамидой”. Алгоритм имеет гарантированную низкую трудоемкость вида и не требует дополнительной памяти.

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

Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду “пирамиды”. На втором этапе осуществляется сортировка “пирамиды”.

Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:

A[1]

A[2] A[3]

A[4] A[5] A[6] A[7]

A[8] A[9] ...

Структура дерева имеет логический характер - в памяти компьютера все элементы массива все равно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка A[2i] и A[2i+1], где i - индекс данного элемента (“предка”).

Элементы массива, являющегося “пирамидой”, обладают следующими дополнительными свойствами:

1. Любой элемент пирамиды A[i] не меньше, чем его элементы-потомки A[2i] и A[2i+1] (соответственно первый элемент обладает максимальным значением):

A[i] >= A[2i],

A[i] >= A[2i+1]

2. Любая подпоследовательность элементов вида A[n\2+1], A[n\2+2], ... A[n] также является пирамидой, обладающей свойствами 1 и 2.

После преобразования массива к форме пирамиды сортировка осуществляется следующим образом:

В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и “укоротим” массив на 1 элемент с “хвоста”. Наибольший элемент массива окажется последним. “Укороченная” последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент A[1] и его потомки - A[2] и A[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент A[1] и наибольший из потомков: max(A[2], A[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом.

Программа сортировки методом пирамиды:

SUB HeapSort STATIC

FOR I = 2 TO MaxRow

PercolateUp I

NEXT I

FOR I = MaxRow TO 2 STEP -1

SWAP SortArray(1), SortArray(I)

PercolateDown I - 1

NEXT I

END SUB

SUB PercolateUp (MaxLevel) STATIC

I = MaxLevel

DO UNTIL I = 1

Parent = I \ 2 ' Get the subscript for the parent node.

IF SortArray(I).Length > SortArray(Parent).Length THEN

SWAP SortArray(Parent), SortArray(I)

I = Parent

ELSE

EXIT DO

END IF

LOOP

END SUB

SUB PercolateDown (MaxLevel) STATIC

I = 1

DO

Child = 2 * I ' Get the subscript for the child node.

IF Child > MaxLevel THEN EXIT DO

IF Child + 1 <= MaxLevel THEN

IF SortArray(Child + 1).Length > SortArray(Child).Length THEN

Child = Child + 1

END IF

END IF

IF SortArray(I).Length < SortArray(Child).Length THEN

SWAP SortArray(I), SortArray(Child)

I = Child

ELSE

EXIT DO

END IF

LOOP

END SUB