Сортировка методом Шелла

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

d=[n/2]

Массив: 23, 8, 5, 65, 47, 34, 1, 6, 13, 52

Шаг 1: d=5 (сортируются элементы, расстояние между которыми пять)

23, 8, 5, 65, 47, 34, 1, 6, 13, 52 –массив не меняется

23, 8, 5, 65, 47, 34, 1, 6, 13, 52

23, 1, 5, 65, 47, 34, 8, 6, 13, 52

23, 1, 5, 65, 47, 34, 8, 6, 13, 52– массив не меняется

23, 1, 5, 65, 47, 34, 8, 6, 13, 52

23, 1, 5, 13, 47, 34, 8, 6, 65, 52

23, 1, 5, 13, 47, 34, 8, 6, 65, 52 – массив не меняется

Шаг 2: d=3 (сортируются элементы, расстояние между которыми три)

23, 1, 5, 13, 47, 34, 8, 6, 65, 52

13, 1, 5, 23, 47, 34, 8, 6, 65, 52

13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется

13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется

13, 1, 5, 23, 47, 34, 8, 6, 65, 52

13, 1, 5, 8, 47, 34, 23, 6, 65, 52

13, 1, 5, 8, 47, 34, 23, 6, 65, 52

13, 1, 5, 8, 6, 34, 23, 47, 65, 52

13, 1, 5, 8, 6, 34, 23, 47, 65, 52– массив не меняется

13, 1, 5, 8, 6, 34, 23, 47, 65, 52 – массив не меняется

Шаг 3: d=2 (сортируются элементы, расстояние между которыми два)

13, 1, 5, 8, 6, 34, 23, 47, 65, 52

5, 1, 13, 8, 6, 34, 23, 47, 65, 52

5, 1, 13, 8, 6, 34, 23, 47, 65, 52– массив не меняется

5, 1, 13, 8, 6, 34, 23, 47, 65, 52

5, 1, 6, 8, 13, 34, 23, 47, 65, 52

5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

5, 1, 6, 8, 13, 34, 23, 47, 65, 52 – массив не меняется

Шаг 4: d=1 (сортируются элементы, расстояние между которыми один)

5, 1, 6, 8, 13, 34, 23, 47, 65, 52

1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 34, 23, 47, 65, 52

1, 5, 6, 8, 13, 23, 34, 47, 65, 52

1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется

1, 5, 6, 8, 13, 23, 34, 47, 65, 52

1, 5, 6, 8, 13, 23, 34, 47, 52, 65

6.5.4 Сортировка «методом пузырька»

Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1].

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: i₁= 23, 8, 5, 65, 47, 34, 1, 6

Шаг 2: i₂₌ 23, 8, 5, 65, 47, 34, 1, 6

5, 8, 23, 65, 47, 1, 34, 6

5, 8, 23, 65, 1, 47, 34, 6

5, 8, 23, 1, 65, 47, 34, 6

5, 8, 1, 23, 65, 47, 34, 6

5, 1, 8, 23, 65, 47, 34, 6

1, 5, 8, 23, 65, 47, 34, 6

Шаг 3: i₃= 1, 5, 8, 23, 65, 47, 34, 6

1, 5, 8, 23, 65, 47, 6, 34

1, 5, 8, 23, 65, 6, 47, 34

1, 5, 8, 23, 6, 65, 47, 34

1, 5, 8, 6, 23, 65, 47, 34

1, 5, 6, 8, 23, 65, 47, 34

Шаг 4: i₄= 1, 5, 6, 8, 23, 65, 47, 34

1, 5, 6, 8, 23, 65, 34, 47

1, 5, 6, 8, 23, 34, 65, 47

Шаг 5: i₅= 1, 5, 6, 8, 23, 34, 65, 47

1, 5, 6, 8, 23, 34, 47, 65

Шейкерная сортировка.

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6

23, 8, 5, 65, 47, 1, 34, 6

23, 8, 5, 65, 1, 47, 34, 6

23, 8, 5, 1, 65, 47, 34, 6

23, 8, 1, 5, 65, 47, 34, 6

23, 1, 8, 5, 65, 47, 34, 6

1, 23, 8, 5, 65, 47, 34, 6

Шаг 2: 1, 23, 8, 5, 65, 47, 34, 6

1, 23, 5, 8, 65, 47, 34, 6

1, 5, 23, 8, 65, 47, 34, 6

Шаг 3: 1, 5, 23, 8, 65, 47, 34, 6

1, 5, 23, 8, 65, 47, 6, 34

1, 5, 23, 8, 65, 6, 47, 34

1, 5, 23, 8, 6, 65, 47, 34

1, 5, 23, 6, 8, 65, 47, 34

1, 5, 6, 23, 8, 65, 47, 34

Шаг 4: 1, 5, 6, 23, 8, 65, 47, 34

1, 5, 6, 8, 23, 65, 47, 34

Шаг 5: 1, 5, 6, 8, 23, 65, 47, 34

1, 5, 6, 8, 23, 65, 34, 47

1, 5, 6, 8, 23, 34, 65, 47

Шаг 6: 1, 5, 6, 8, 23, 34, 65, 47

1, 5, 6, 8, 23, 34, 47, 65

Сортировка выбором.

При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение.

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6

1, 8, 5, 65, 47, 34, 23, 6

Шаг 2: 1, 8, 5, 65, 47, 34, 23, 6

1, 5, 8, 65, 47, 34, 23, 6

Шаг 3: 1, 5, 8, 65, 47, 34, 23, 6

1, 5, 6, 65, 47, 34, 23, 8

Шаг 4: 1, 5, 6, 65, 47, 34, 23, 8

1, 5, 6, 8, 47, 34, 23, 65

Шаг 5: 1, 5, 6, 8, 47, 34, 23, 65

1, 5, 6, 8, 23, 34, 47, 65