Сортировка методом пузырька.

Одним из самых простых методов сортировки является так называемый метод пузырька. Для того чтобы легче понять идею этого метода, представим, что сортируемый массив расположен вертикально (пусть индексы возрастают снизу вверх) и в процессе сортировки «более легкие» элементы массива всплывают наверх наподобие пузырьков воздуха в жидкости. Что понимать под «более легким» элементом зависит от того, в каком порядке сортируются элементы массива. Если элементы сортируются в порядке возрастания, то «более легким» из двух элементов считается элемент с большим значением. Если же массив сортируется в порядке убывания, то «более легким» из двух элементов считается элемент с меньшим значением.

При первом проходе массива снизу вверх, берется текущий элемент массива и сравнивается с следующим элементом. Если текущий элемент «легче» следующего, то эти элементы меняются местами. После таких действий самый «легкий» элемент всплывает наверх, т.е. оказывается последним элементом массива. Можно сказать, что теперь массив разбит на две части: отсортированную часть, состоящую только из последнего элемента массива и не отсортированную часть, состоящую из первых n-1 элементов массива, где n - число элементов массива.

Далее повторяем аналогичные действия для не отсортированной части массива. После этого самый легкий элемент массива в не отсортированной части переместится на n-1 место. Отсортированная часть уже будет состоять из двух элементов (n и n-1 элементы).

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

Иллюстрация работы алгоритма пузырьковой сортировки представлена на рис.7.3(а). Алгоритм представлен блок-схемой на рис.7.4(а).

Заметим, что в примере, представленном на рисунке 7.3(а), алгоритм пузырьковой сортировки выполнил четыре итерации разделения массива на отсортированную и не отсортированную части. Однако после третей итерации массив уже стал отсортированным, и можно было остановить работу алгоритма. Подобные случаи возникают, когда в массиве есть отсортированные участки. Обработка таких случаев возможна, если запоминать позицию текущего элемента, с которым был осуществлен последний обмен. Эта позиция будет определять границу отсортированной части массива. Иллюстрация работы модифицированного таким образом алгоритма пузырьковой сортировки представлена на рис.7.3(б), блок-схема алгоритма - на рис.7.4(б).

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

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

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

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

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

Идея сортировки выбором состоит в том, что на 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.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²).

Быстрая сортировка

Алгоритм быстрой сортировки является, по-видимому, самым эффективным алгоритмом сортировки массивов. В этом алгоритме для сортировки элементов массива X[1],X[2],...,X[N] из этих элементов выбирается некоторый элемент, значение которого берется в качестве опорного значения v, относительно которого переупорядочиваются элементы массива. Переупорядочивание заключается в том, чтобы для некоторого индекса j все элементы X[1],...,X[j] имели значение меньше v, а все элементы X[j+1],...,X[N] имели значение больше или равно v. Затем процедура рекурсивно применяется к частям массива, состоящим из элементов X[1],...,X[j] и X[j+1],...,X[N]. Желательно выбрать опорное значение так, чтобы сортируемый массив разбивался на две примерно равные части.

На рис.7.11 показаны шаги выполнения процедуры быстрой сортировки, выполняемые для массива, состоящего из чисел 3,1,4,1,5,9,2,6,5,3. На каждом шаге значение v выбирается как наибольшее значение из двух самых левых различных элементов части текущей части массива. Сортировка завершается, когда части массива, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые элементы.

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

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

Сортировка слиянием

Если данные хранятся в файле и объем данных превышает размер оперативной памяти, то для сортировки таких данных можно воспользоваться сортировкой слиянием. Основная идея сортировки слиянием проиллюстрирована на рис.7.14. В данном случае исходный файл F0 разбивается на две части, которые могут быть помещены в оперативную память (в общем случае число таких частей может быть больше двух). Далее обе части сортируются любым из методов внутренней сортировки и записываются на диск. В данном примере запись осуществляется в рабочие файлы F1 и F2. Однако можно было осуществить запись отсортированных частей файла на место исходного файла. Далее отсортированные части файла сливаются в одну.

Слияние двух отсортированных файлов в один осуществляется следующим образом:

1. В качестве текущих элементов первого и второго файла принять первые элементы в этих файлах. Результирующий файл пуст.

2. Если значение текущего элемента первого файла больше значения текущего элемента второго файла, то в результирующий файл записать значение текущего элемента второго файла и в качестве текущего элемента второго файла принять следующий элемент в этом файле

3. Если значение текущего элемента первого файла меньше или равно значению текущего элемента второго файла, то в результирующий файл записать значение текущего элемента первого файла и в качестве текущего элемента первого файла принять следующий элемент в этом файле

4. Если достигнут конец первого файла, то все элементы второго файла переписать в результирующий файл.

5. Если достигнут конец второго файла, то все элементы первого файла переписать в результирующий файл.

Этапы слияния исходных файлов F1 и F2 в результирующий файл F3 (см. рис.7.14) представлены в табл.7.1.

Таблица 7.1