Пирамидальная сортировка

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

1. Общее быстродействие O(n^2).

2. Сортировка происходит на месте.

3. Неустойчивая.

4. Поведение неестественное.

Сортировка вставками не относится к категории быстродействующих, поскольку единственный вид операции обмена, который она использует, выполняется над двумя соседними элементами, в связи с чем элемент может передвигаться вдоль массива лишь на одно место за один раз. Например, если наибольший элемент оказывается в конце массива, потребуется сделать N шагов, чтобы поместить его в надлежащее место. Сортировка методом Шелла представляет собой простейшее расширение метода вставок, быстродействие которого выше за счет обеспечения возможности обмена местами элементов, которые находятся далеко один от другого (элементы перемещаются большими скачками).

Идея метода:

В исходном массиве выделяю группы элементов. Каждая группа сортируется методом вставки. По ходу работы алгоритма размеры таких групп увеличиваются, пока все элементы массива не войдут в одну группу. Группой массива называется последовательность элементов, номера которых образуют арифметическую прогрессию с разностью h, которая называется шагом группы.

Основной вопрос - это выбор последовательности шагов. Существует достаточное количество исследований этого вопроса, и предложено большое количество методик выбора этой последовательности для разного числа элементов. Самый простой способ: h = n/2-1.

Один из способов реализации сортировки методом Шелла заключается в том, что для каждой выделенной группы элементов независимо используется сортировка вставками на каждом из h подмассивов. Несмотря на очевидную простоту этого процесса, возможен еще более простой подход именно благодаря тому, что подмассивы независимы. В процессе h-сортировки массива мы просто вставляем элемент среди предшествующих ему элементов в соответствующем h-подмассиве, перемещая большие по значению элементы вправо. Эта задача решается путем использования программы сортировки вставками, при которой каждый шаг перемещения по массиву в сторону увеличения или уменьшения равен h, но не равен 1. С учетом данного обстоятельства программная реализация сортировки методом Шелла сводится всего лишь к тому, что для каждого значения шага осуществляется проход по массиву, характерный для сортировки вставками.

Общее быстродействие O(n*log(n)). Быстрая сортировка.

1. Сортировка на месте.

2. Неустойчивая.

3. Поведение неестественное.

Назовем пирамидой бинарное дерево высотой k, в котором все узлы имеют максимальный уровень k или k-1, то есть дерево является сбалансированным. При этом уровень k-1 заполнен полностью, а уровень k заполнен слева направо.

Для пирамиды выполняется свойство: каждый элемент меньше либо равен родителю. Самым простым способом хранения пирамиды является массив. Соответствие между графическим представлением пирамиды и массивом осуществляется по правилам: в a[0] помещается корень дерева. Левый и правый сыновья элемента a[i]-го хранятся в ячейках, a[2*i+1] и a[2*i+2]. Таким образом, для массива, хранящего в себе пирамиду, выполняется свойство, что a[i]>=a[2*i+1] и a[i]>=a[2*i+2].

Такой способ хранения имеет следующие преимущества:

• Для организации не используется дополнительная память.
• Узлы хранятся от вершины и далее вниз уровень за уровнем. Узлы одного уровня хранятся в массиве слева направо.

Чтобы воспользоваться пирамидальной сортировкой, необходимо выполнить 2 действия:

• по исходному массиву построить пирамиду,
• произвести сортировку.

Дата добавления: 2014-01-11