Дан неупорядоченный массив чисел: 33, 55, 25, 7, 16, 45, 22,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

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

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

Соответственно имеем формулу , либо же другими словами: сумма частей (2i - 3) от i, где i = n, пока i gt; 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