Обзор алгоритмов сортировки Шелла, сортировки методом слияния и быстрой сортировки

Эта статья является обзором наиболее известных алгоритмов сортировки, в ней представлено описания алгоритмов сортировки на языке программирования java, анализ их базовых свойств, их сравнение, а также выкладки о том, в каком случае какой алгоритм лучше использовать.

Для начала опишем алгоритм сортировки Шелла, который основан на сортировке вставками. Алгоритм сортировки вставками часто применяют игроки в карты для упорядочивания своих карт, состоит он в следующем: они просматривают все свои карты по одной и вставляют каждую из них на своё место из уже просмотренных.

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

Основная идея состоит в переупорядочивании массива таким образом, чтобы каждые h-е элементы составляли упорядоченную последовательность, где h = (1, 4, 13, 40, …) [1, с. 241].

Реализация алгоритма сортировки Шелла представлена на рисунке 1.

Рисунок 1. Реализация алгоритма сортировки Шелла

Проведя анализ алгоритма Шелла можно прийти к выводу, что время выполнения алгоритма в худшем случае равно O(). К этому выводу приходим эмпирически, проведя многочисленные эксперименты.

Далее рассмотрим сортировку слиянием. Основная идея сортировки слиянием заключается в самой операции слияния. Слияние – объединение двух отсортированных массивов в один большой упорядоченный массив. Для данного алгоритма очень подходит фраза: «разделяй и властвуй». Ведь весь алгоритм можно представить простой последовательностью шагов [2, с. 5]:

·     Взять массив и разделить его пополам;

·     Отсортировать левую часть;

·     Отсортировать правую часть;

·     Объединить массивы, используя операцию слияния.

В итоге приходим к простому рекурсивному алгоритму. Для того, чтобы реализовать алгоритм сортировки слиянием, нам необходимо реализовать сам метод слияния. Реализация метода слияние приведена на рисунке 2.

Рисунок 2. Реализация метода слияния

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

·     Левая половина закончилась;

·     Правая половина;

·     Текущий ключ из правой половины меньше текущего ключа из левой;

·     Текущий ключ из правой половины больше, либо равен, текущему ключу из левой.

После этого, имея реализацию метода слияния, довольно просто создать рекурсивный метод сортировки. Реализация метода сортировки представлена на рисунке 3.

Рисунок 3. Реализация метода сортировки слиянием

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

,                                                                                (1)

O(n) – время выполнения алгоритма слияния

 – время выполнения сортировки половины массива [2, с. 2].

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

Последний оставшийся метод сортировки, это быстрая сортировка.

Это наиболее популярная сортировка, и ее популярность объясняется не трудной реализацией и скоростью выполнения [1, с. 268].

Базовый алгоритм сортировки является дополнением алгоритма сортировки слиянием, она также работает, выполняя разбиение массива на два подмассива, с последующей сортировкой полученных подмассивов. Разница между быстрой сортировкой и сортировкой слиянием заключается в том, что мы не получаем два упорядоченных подмассива которые затем объединяем в один, а переупорядочиваем массив так, что после сортировки двух подмассивов исходный массив также становится упорядоченным.

Основа метода – процесс разбиения, метод переупорядочивает массив таким образом, чтобы выполнялись следующие условия:

·     Элемент a[j] находится на своём месте;

·     Ни один элемент от a[lo] до a[j-1] не больше, чем a[j];

·     Ни один элемент от a[j+1] до a[hi] не меньше, чем a[j].

Реализуем метод разбиения. Реализация метода представлена на рисунке 4.

Рисунок 4. Реализация метода разбиения

После того, как реализован метод разбиения, можем описать алгоритм самой сортировки. Описание алгоритма сортировки представлено на рисунке 5.

Рисунок 5. Реализация быстрой сортировки

Так как, в основе быстрой сортировки лежит метод сортировки слиянием, то время выполнения алгоритма быстрой, также как и сортировки вставками равно . Важным отличием метода быстрой сортировки, от сортировки вставками то, что нам не требуется дополнительная память, и при этом такая же производительность [1, с. 272].