Квадратичные сортировки
Сортировка - это перестановка элементов массива (списка) в заданном порядке.
Метод пузырька (пузырьковая сортировка), или сортировка простыми обменами).
Бессмертная классика жанра. Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец.
Источник
Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
F=0
ЦИКЛ ДЛЯ I=1 ДО N-J-1 ШАГ 1
ЕСЛИ A[I] > A[I+1] ТО
ОБМЕН A[I],A[I+1]
F=1
СЛЕДУЮЩЕЕ I
ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА // если за проход не было обменов,
// то значит все элементы
// расставлены в нужном порядке
СЛЕДУЮЩЕЕ J
Сложность данного алгоритма:
\(\displaystyle O(n^{2})\).
Дополнительная полезная информация:
статья на википедии.