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

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

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

Код реализации этого алгоритма представлен на рисунке 1 [3, с. 57].

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

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

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

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

Теперь рассмотрим сортировку слиянием. Этот алгоритм основан на простой операции слияния, но что такое слияние. Слияние – объединение двух упорядоченных массивов для получения одного большого упорядоченного массива. Эта операция приводит к простому рекурсивному методу сортировки суть которого выражается в простом алгоритме: необходимо взять массив разделить его пополам, отсортировать сначала левую часть массива, затем правую, а после этого соединить два упорядоченных массива [1, с. 252].

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

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

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

Для выполнения слияния метод вначале копирует входной массив в вспомогательный, а затем сливает их во входной. В процессе слияние возможны 4 ситуации (все они учтены и приведены в цикле for рис. 3):

·     Левая половина закончилась (берем данные из правой)

·     Правая половина закончилась (берем данные из левой)

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

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

Теперь имея метод слияние реализовать алгоритм сортировки довольно просто, только важно не забыть выделить память для вспомогательного массива. Реализация метода сортировки представлена на рисунке 4.

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

После того, как мы привели описания каждого из алгоритмов проведём их анализ.

Анализируя алгоритм Шелла можно прийти к выводу, что время выполнения сортировки не обязательно квадратично, количество сравнений в алгоритме в худшем случае пропорционально . К этому выводу приходим из многочисленных экспериментов, которые дают основание полагать, что среднее количество сравнений на один шаг может быть равно , и данное свойство не зависит от входных данных. Таким образом время исполнения алгоритма сортировки Шелла равна O() [3, с. 2].

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

,                                                                                       (1)

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

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

Как вы видим в итоге получаем рекуррентную формулу. Опуская сложные математические выкладки приходим к тому, что 

Таким образом время выполнения алгоритма сортировки слиянием равно .

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