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

Еще один метод сортировки это метод вставками. Свое название метод получил из-за того, что на j-ой итерации происходит вставка j-го элемента массива X в нужную позицию среди элементов X[1],X[2],...,X[j-1], которые уже отсортированы. После выполнения этой вставки первые j элементов массива будут отсортированы. Подобным образом игроки упорядочивают свои карты, беря по одной. Работа алгоритма сортировки вставками проиллюстрирована на рис.7.5, алгоритм представлен блок-схемой на рис.7.6.

Время выполнения алгоритма сортировки вставками в худшем случае равно O(n²).

7.2.3.Сортировка выбором

Идея сортировки выбором состоит в том, что на j-ой итерации элементы массива разбиты на не отсортированную часть (элементы X[1],...,X[j]) и отсортированную часть (элементы X[j+1],...,X[n]). Среди первых j элементов массива X, составляющих не отсортированную часть массива, ищется наибольший элемент, пусть это i-ый элемент. После этого j-ый и i-ый элементы массива меняются местами. В результате отсортированная часть массива увеличивается на один элемент (элементы X[j],...,X[n]), а не отсортированная - уменьшается на один элемент (элементы X[1],...,X[j-1]). Выполнив n-1 таких итераций, получим массив, отсортированный в порядке возрастания.

Работа алгоритма сортировки выбором проиллюстрирована на рис.7.7, блок-схема алгоритма - на рис. 7.8.

Время выполнения алгоритма сортировки выбором в худшем случае равно O(n²).

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

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

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

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

• каждый элемент массива с номером i соответствует вершине с номером i.;

• первый элемент массива соответствует корню дерева;

• из вершины с номером i выходят дуги в вершины с номерами i2 и i2+1 (такие вершины называются потомками вершины i). Если i2 или i2+1 больше числа вершин, то соответствующей дуги нет.

На первом шаге алгоритма пирамидальной сортировки бинарное дерево преобразуется в пирамиду. В пирамиде выполняется следующее условие: значение i-го элемента массива, соответствующего i-ой вершине дерева, из которой есть выходящие дуги в вершины k и (или) m, больше чем значения k-го и (или) m-го элемента массива.

После построения пирамиды максимальный элемент массива соответствует корню и находится на первом месте. После этого выполняется разрушение пирамиды - меняются местами первый и последний элементы массива.

После рассмотренных действий массив X, состоящий из n элементов, разбился на две части: не отсортированную и отсортированную. Не отсортированная часть массива состоит из элементов X[1],X[2],...,X[n-1]. Отсортированная часть массива состоит из единственного элемента X[n].

Далее процесс построения и разрушения пирамиды применяется к не отсортированной части массива. В результате не отсортированная часть массива будет состоять из элементов X[1],X[2],...,X[n-2], а отсортированная - из элементов X[n-1],X[n].

Выполнив n итераций построения и разрушения пирамиды, получим массив, отсортированный в порядке возрастания.

Алгоритм пирамидальной сортировки представлен блок-схемами на рис.7.10.

Пирамидальная сортировка эффективнее, чем сортировка выбором. Это связано с тем, что построение пирамиды после ее разрушения осуществляется за время O(log₂m), где m-число элементов в не отсортированной части массива, в то время как поиск наибольшего элемента в сортировке выбором осуществляется медленнее, за время O(m).

Рассмотрим процесс построения пирамиды после ее разрушения более подробно. На рис.7.11 данный процесс проиллюстрирован для не отсортированной части массива, состоящей из 14 следующих элементов: 8, 11, 14, 7, 9, 13, 12, 2, 3, 4, 5, 6, 1, 10. Процесс построения пирамиды состоит из трех шагов. На каждом шаге для текущей вершины выбирается потомок с большим значением, и это значение сравнивается со значением текущей вершины. Если значение текущей вершины меньше чем значение выбранного потомка, то производится обмен данными значениями и выбранный потомок принимается в качестве текущей вершины.

На первом шаге в качестве текущей вершины выступает первая вершина. Потомками первой вершины являются вторая и третья вершины (см. рис.**). Значение третьей вершины равно 14, что больше 11 - значения второй вершины, поэтому выбирается третья вершина. Далее сравнивается значение текущей вершины (8) и третьей вершины (14). Значение текущей вершины меньше значения третьей вершины, поэтому происходит обмен данными значениями и третья вершина принимается в качестве текущей вершины.

Аналогично выполняется второй и третий шаги построения пирамиды после ее разрушения (см. рис.**). После выполнения данных шагов не отсортированная часть массива преобразована в пирамиду и состоит из следующих 14 элементов: 14, 11, 13, 7, 9, 8, 12, 2, 3, 4, 5, 6, 1, 10.

Отметим, что число шагов необходимых для построения пирамиды не может быть больше чем длина пути от корня до листьев дерева. А такая длина равна значению log₂m округленному до наименьшего целого числа. Таким образом, построение пирамиды после ее разрушения осуществляется за время O(log₂m).

Время выполнения алгоритма пирамидальной сортировки в худшем случае равно O(nlog₂n). Таким образом, данная сортировка эффективнее всех ранее рассмотренных сортировок. Напомним, что все ранее рассмотренные сортировки имели порядок функции временной сложности O(n²).