9. Квадратичные сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. По невозрастанию/неубыванию. Сорт раздел по количеству действий и по принципу сортировка.

количество обменов/сравнений кратно N*N

Сортировка посредством выбора/ обмена.

Самый простой способ сортировки. Его идея заключается в следующем: ищется минимальный элемент массива и ставиться на первое место. Затем ищется наименьший элемент среди элементов a[2]..a[N] и ложится в a[2]. Обобщая: на i-м шаге в a[i]

Сортировка "пузырьком"

Представим себе вертикальный массив, пронумерованный сверху вниз. Наиболее легкие элементы, т.е. элементы с меньшими значениями, поднимаются вверх (как бы "всплывают" наподобие пузырька). Делается это так.

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

Время выполнения сортировок посредством выбора и "пузырьком" составляет N*(N-1)/2 , что равно O(N2).

Сортировка вставками

Будем менять элемент k с левым соседом до тех пор, пока он не встанет на свое место:

Сортировка Шелла / оболочечная. на основе сортировки вставками.

1)Сортируем вставкой каждую N/2 групп из 2х элементов

2)Сортируем каждую из N/4 групп по 4 элемента

3)....

4)сортируем каждую 1 группуц из N элементов

Существенно уменьш кол-во обменов -> N*lnN*liN

12 8 14 6 4 9 1 8 13 5 11 3 18 3 10 9

12 5 11 3 4 3 1 8 13 8 14 6 18 9 10 9

4 3 1 3 12 5 10 6 13 8 11 8 18 9 14 9

4 3 1 3 12 5 10 6 13 8 11 8 18 9 14 9

1 3 4 3 10 5 11 6 12 8 13 8 14 9 18 9

1 3 3 4 5 6 8 8 9 9 10 11 12 13 14 18

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

Сортировка Хоара.

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. По невозрастанию/неубыванию. Сорт раздел по количеству действий и по принципу сортировка.

Рекурсивная.

N*log2(N) к-во действий

Метод Хоара.

Сортируемый участок обрабатываем так:

ищется средний элемент(по медиане, по значению, по индексу, берётся число и ставится на своё место(слева<=число<=справа), слева ищутся элементы больше числа, справа-меньше.

Процесс идёт жо тех пор, пока в левой не окажутся все маленькие, справа - большие. Операция повторяется рекурсивно для каждого из двух участков.

CN = 2CN/2+N - наилучший случай. 2N ln N сравнений.

Очень медленно с упорядоченными массивами. Работает медленно на малых последовательностях. => Объед квадратичную и быструю сортировку.

48 51 37 18 11 122 16 81

16 51 37 18 11 122 48 81

16 11 37 18 51 122 48 81

[16 11] 18 [37 51 122 48 81]

[11 16] 18 [37 51 81 48 122]

11 16 18 [37 51 81 48] 122 [ ]

11 16 18 [37 48 81 51] 122 [ ]

11 16 18 [37 48 81 51] 122 [ ]

11 16 18 [37 48] 51 [81] 122 [ ]

11 16 18 37 48 51 81 122