Алгоритм сортировки Шейкером

1. Задать массив из n чисел.

2.1 Левая_граница = 0.

2.2. Правая_граница = n.

2.3. Повторять

2.3.1. Движение слева направо:

1) Для i = Левая_граница; i < Правая_граница; i++

Если элементы i-тый и (i+1)-вый стоят неправильно,

a) Поменять их местами;

b) Номер = i.

2.3.2. Движение справа налево:

1) Правая_граница = Номер.

2) Для i = Правая_граница; i > Левая_граница; i--

Если элементы i-тый и (i+1)-вый стоят неправильно,

a) Поменять их местами;

b) Номер = i.

2.3.3. Левая_граница = Номер.

Пока Левая_граница < Правая_граница.

3. Вывести отсортированный массив.

4. Закончить.

Анализ шейкерного алгоритма довольно сложен. Число сравнений и пересылок в худшем случае пропорционально n², т.е. его сложность равна О(n²).

3.3. Эффективные методы внутренней сортировки

К этим методам можно отнести следующие.

1) Сортировку Шелла;

2) Быструю сортировку;

3) Пирамидальную сортировку (с помощью двоичного дерева), алгоритм которой будет рассмотрен позднее, когда будут изучаться деревья.

3.3.1. Сортировка Шелла

Метод является ускоренным вариантом сортировки вставками. При этом ускорение достигается за счет увеличения расстояния, на которое перемещаются элементы. Исходный массив делится на d частей, содержащих n/d элементов каждый (последний подмассив может быть короче). Подмассивы содержат элементы с номерами [0, d, 2 d и т.д.], [1, d +1, 2 d +1 и т.д.], [2, d + 2, 2 d +2 и т.д.] и т.д.

Вначале сравниваются и упорядочиваются с помощью алгоритма вставок элементы, отстоящие один от другого на расстоянии d, т.е. имеющие номера 0 и 1, d и d + 1, 2 d и 2 d + 1 и т.д. Затем процедура повторяется при меньших значениях d, например, d/2. Завершается алгоритм упорядочением элементов при d=1, то есть обычной сортировкой вставками. Мы рассмотрим сортировку Шелла для начального значения d, равного n/2, и будем последовательно уменьшать его вдвое.

Алгоритм сортировки Шелла

1. Задать массив А из n чисел.

2. Выполнять

2.1. d = n / 2.

2.2. Для i от 0 до n – d с шагом d

2.2.1. j = i.

2.2.2. x = A_i

2.2.3. Пока ( j ≥ d) И (A[j] > A[j + d])

a) A[j] = A[j + d]

b) j = j – d.

2.3. d = d / 2.

Пока d > 0.

3. Вывести массив А.

В зависимости от начального значения и закона изменения расстояния d рассматриваемый метод может работать быстрее или медленнее. Так, если d является степенью 2 (64, 32, …, 2, 1), то до последнего прохода элементы с четными индексами никогда не сравниваются с теми, у которых индексы нечетные. Поэтому при последнем проходе возможны перемещения на большие расстояния.

В ряде работ предлагается задавать значение d, равным 2^k – 1, или сложнее, либо вычислять размеры подмассивов заранее и хранить их в виде массива значений d.

Анализ сортировки Шелла довольно сложен. Число сравнений и пересылок в худшем случае пропорционально n², т.е. его сложность равна О(n²), а в лучшем - О(n log n). Вообще рассмотренный метод эффективнее сортировки вставками, но уступает быстрой сортировке.

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

Метод был предложен английским программистом Хоором. Он использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Алгоритм является разновидностью «пузырьковой» сортировки и реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.

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

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

Общий алгоритм можно представить так.

1. Из массива выбирается некоторый опорный элемент, например,

Опорный = a[n/2].

2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, или равные Опорному, - вправо.

3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.

4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.

В конце получится полностью отсортированная последовательность.