Question

Дан неупорядоченный массив чисел: 33, 55, 25, 7, 16, 45, 22, 30, 41, 83,12, 17,31, 77 Выполнить сортировку массива с помощью метода методом Шейкерной сортировки. Описать последовательность действий. Выполнить подсчет сравнений.

Answer 1

I. Последовательность действий

- Выделить массив от a[l] до a[r], где a - сортируемый массив, а l & r - крайний левый и крайний правый сортируемый елемент

- Провести сравнение елементов попарно двигаясь слева на право, если первый елемент больше второго - необходимо поменять их местами

- Откинуть крайнеправый елемент из сортируемого участка

- Провести сравнение елементов попарно двигаясь справа на лево, если первый елемент меньше второго - необходимо поменять их местами

- Откинуть крайне левый элемент из сортируемого участка

- Повторить с начала пока не останется сортируемых элементов

II. Оптимизация

Выполнение абсолютно всех проверок (прохождение по всем под массивам) не является обязательным при наличии механизма определяющего является ли массив отсортированным. Таковым может служить флаг, который будет выставлен при отсутствии перемещений элементов в выделенном под массиве на текущей итерации сортировки. Если он выставлен, следующая итерация - не выполняется.

III. Пример сортировки

Элементы что находятся в текущем под массиве - выделены [] скобками.

Элементы что сравниваются в текущей итерации выделены ()

[(33 55) 25 7 16 45 22 30 41 83 12 17 31 77] | 33 < 55 -> пропускаем

[33 (55 25) 7 16 45 22 30 41 83 12 17 31 77] | 55 > 25 -> меняем местами

...

7 12 16 [17 22 25 30 31 (33 41) 45] 55 77 83 | 33 < 41 -> пропускаем

7 12 16 [17 22 25 30 31 33 (41 45)] 55 77 83 | 41 < 45 -> пропускаем

Так как на протяжении всего прохода по под массиву не было перемещений -> сортировка завершена.

(Полное решение представлено в прикрепленной картинке)

Кол-во сравнений при оптимизации сортировки: 71

Если считать кол-во сравнений в сортировке без оптимизации (либо в самом неудачном раскладе сорируемого массива) то его можно будет посчитать так:

кол-во сравнений 2n - 3 - для прохода по подмостиву туда и обратно (n - кол-во элементов массива)

кол-во сравнений в сортировке - сумма сравнений для прохода по каждому из под массивов туда и обратно

кол-во под массивов в массиве будет равно n / 2

Соответственно имеем формулу $\sum_{i=n}^{i>1}(2n-3)_{i};i=i-2$, или же другими словами: сумма элементов (2i - 3) от i, где i = n, пока i > 1, когда i = i - 2.

Ну и переведем её на наш пример:

n = 14

i = n

(2 * 14 - 3) + (2 * 12 - 3) + (2 * 10 - 3) + (2 * 8 - 3) + (2 * 6 - 3) + (2 * 4 - 3) + (2 * 2 - 3) =

25 + 21 + 17 + 13 + 9 + 5 + 1 = 91

Кол-во сравнений при оптимизации сортировки: 91

Answer 2

Метод шейкерной сортировки, также известный как сортировка перемешиванием (cocktail shaker sort), представляет собой улучшенную версию пузырьковой сортировки. Он работает, прокручивая массив в обоих направлениях, сравнивая и меняя элементы, чтобы переместить наибольший элемент в правую часть массива и наименьший элемент в левую часть. Процесс повторяется до тех пор, пока массив не будет полностью отсортирован.

Давайте выполним сортировку массива [33, 55, 25, 7, 16, 45, 22, 30, 41, 83, 12, 17, 31, 77] с помощью шейкерной сортировки:

1. Начальное состояние массива: [33, 55, 25, 7, 16, 45, 22, 30, 41, 83, 12, 17, 31, 77].

2. Повторяем следующие шаги до тех пор, пока не будет выполнено ни одно обменное действие (т.е., массив окажется отсортированным).

   Первый проход слева направо:

   • Сравниваем элементы 33 и 55. Нет обмена.
   • Сравниваем элементы 55 и 25. Обмениваем их: [33, 25, 55, 7, 16, 45, 22, 30, 41, 83, 12, 17, 31, 77].
   • Сравниваем элементы 55 и 7. Обмениваем их: [33, 25, 7, 55, 16, 45, 22, 30, 41, 83, 12, 17, 31, 77].
   • Продолжаем аналогично, пока наибольший элемент 83 не окажется в правой части массива.
   • Полученный массив: [33, 25, 7, 55, 16, 45, 22, 30, 41, 31, 12, 17, 77, 83].

   Первый проход справа налево:

   • Сравниваем элементы 83 и 77. Нет обмена.
   • Сравниваем элементы 77 и 17. Обмениваем их: [33, 25, 7, 55, 16, 45, 22, 30, 41, 31, 12, 77, 17, 83].
   • Продолжаем аналогично, пока наименьший элемент 7 не окажется в левой части массива.

   Второй проход слева направо:

   • Сравниваем элементы 33 и 25. Обмениваем их: [25, 33, 7, 55, 16, 45, 22, 30, 41, 31, 12, 77, 17, 83].
   • Продолжаем аналогично, пока наибольший элемент 83 не окажется в правой части массива.

   Второй проход справа налево:

   • Сравниваем элементы 83 и 77. Нет обмена.
   • Сравниваем элементы 77 и 17. Обмениваем их: [25, 33, 7, 55, 16, 45, 22, 30, 41, 31, 12, 17, 77, 83].
   • Продолжаем аналогично, пока наименьший элемент 7 не окажется в левой части массива.

3. Массив полностью отсортирован: [25, 33, 7, 55, 16, 45, 22, 30, 41, 31, 12, 17, 77, 83].

Количество сравнений можно подсчитать следующим образом: на каждом проходе (слева направо и справа налево) совершается n-1 сравнений, где n - количество элементов в массиве. В нашем случае, n = 14, так что общее количество сравнений будет 2 * (14-1) = 26.

Итак, массив отсортирован, и количество сравнений равно 26.