2. Сортировка квадратичным выбором

48 35 44 17 23 33 41 10 14 20 22 30 5 12 6 17

Массив разбивается на части по sqrt(n)

48 35 44 17 | 23 33 41 10 | 14 20 22 30 | 5 12 6 17

В каждой группе отыскивается максимальный элемент.

4835 44 17 | 23 334110 | 14 20 2230| 5 12 617

Из этих элементов формируется новая группа

48 41 30 17

В ней отыскивается максимальный

48 41 30 17

Он будет максимальным в массиве

48

Этот элемент извлекается

На следующем шаге 48 не учитывается, находится предпоследний: 44 и т.д. Число элементов в группах уменьшается, поэтому отыскивать максимальный проще.

Время работы: N*sqrt(N)

3. Сортировка кубическим выбором

Массив дважды разбивается на группы по sqrt(n).

Время: N*sqrt(N,3)

7. Методы сортировки вставками

   1. Сортировка простыми вставками (в список)

Вставляем элементы так, чтобы список был упорядочен.

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

17 | 7 9 4 6 20 15 5

7 17 | 9 4 6 20 15 5

7 9 17 | 4 6 20 15 5

4 7 9 17 | 6 20 15 5

4 6 7 9 17 | 20 15 5

4 6 7 9 17 20 | 15 5

4 6 7 9 15 17 20 | 5

4 5 6 7 9 15 17 20 |

Количество этапов: n-1

Количество сравнений в лучшем случае: n-1 (если массив упорядочен)

Количество сравнений в худшем случае: n^2/2 (если обратно упорядоченный.

В среднем: n^2/4.

2. Сортировка двухпутевыми вставками

| 11 16 8 14 10 13

x x x x x 11 x x x x x x

x x x x x 11 16 x x x x x

x x x x 8 11 16 x x x x x

x x x x 8 11 14 16 x x x x

x x x 8 10 11 14 16 x x x x

x x x 8 10 11 13 14 16 x x x

Недостаток: требуется удвоить размер памяти для хранения результата.

Среднее количество сравнений: n^2/4

Среднее количество сдвигов: n^2/2 (в 2 раза меньше, чем в предыдущем методе)

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

Используется метод бинарного поиска при вставке элемента.

4 7 9 12 14 16 2022 23 30 33 38 41 42 48

Поступило число 15: 4 7 9 1214 x162022 23 30 33 38 41 42 48

Переменные:

границы фрагмента L,R

текущая позиция i.

Среднее число сравнений: n*log(n,2)

Количество сдвигов такое же.

8. Методы обменной сортировки

   1. Пузырьковое всплытие

Выстраивают элементы сверху вниз. Берут нижний элемент, сравнивают с предыдущим, если порядок нарушен, меняют местами. В результате первого прохода максимальный элемент оказывается наверху. На втором проходе снова меняют местами и до предпоследнего.

n-1 проходов.

24 54 54 54 54

54 24 43 43 43

43 43 24 42 42

35 42 42 35 35

28 35 35 24 28

42 28 28 28 24

В худшем случае количество сравнений: n^2/2

В среднем: n^2/4

2. Шейкер-сортировка

Чередуется 2 этапа: как у всплытия и как у погружения.

26 21 54 17 35 42

35 17 42 21 26 54

17 35 21 42 26 54

17 21 35 26 42 54

17 21 26 35 42 54

9. Распределяющая сортировка

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

1. Сортировка распределением со старших разрядов

Допустим, есть 4-разрядные числа, распределим их на 10 групп по 1-ому разряду. Далее по второму разряду и т.д.

Количество этапов: число разрядов. Каждый элемент на каждом этапе нужно распределить.

Всего пересылок: n*R (R-разрядность чисел)

2. Сортировка распределением с младших разрядов

Начинаем с конца числа. Относительный порядок чисел внутри группы должен сохраниться.

Далее распределяем на 10 групп по 2-ому разряду, но не внутри групп, а во всём массиве целиком. И т.д. До крайнего левого разряда.

25 78 16 34 80 42 04

По крайнему разряду: 80 42 34 04 25 16 78

По второму справа разряду: 04 16 25 34 42 78 80

3. Карманная сортировка с двумя массивами

Эффективны, если числа относятся к подряд расположенным значениям ключей.

Пример:

Находим минимальный элемент, 12. Достраиваем от 12 остальные элементы.

0 1 2 3 4 5 6 7 8 9

14 19 15 12 13 21 16 18 17 20

12 14

12 14 19

12 13 14 15 19

12 13 14 15 18 19 20

12 13 14 15 16 17 18 19 20 21

Недостаток: требуется удвоение памяти

Достоинство: количество пересылок n, где n — число ключей.

4. Карманная сортировка с одним массивом

1 2 3 4 5 6 7 8 9 10

4 7 5 2 3 9 1 8 10 6

2 4

7 2

1 7

3 56 6

9 10

1 2 3 4 56 7 8 9 10

Количество обменов в худшем случае n.

10. Сортировка слиянием

    1. Простое слияние

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

Пример:

5 9 12 17

7 8 10 15 20 22

Сортируем:

5 7 8 9 10 12 15 17 20 25

Количество пересылок: n1+n2 (суммарное число элементов в обоих массивах)

19 10 35 14 20 18 28 12

Берём первый и последний элементы, сливаем

12 19

Берём второй и предпоследний

(10 28)

(18 35 ) (14 20)

(10 12 19 28) (14 18 20 35)

( 10 12 14 18 19 20 28 35 )

Количество сравнений в худшем случае: n*log(N-1,2)

В лучшем случае: N*log(N-1,2) / 2