Пузырьковая сортировка.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву.
За каждый проход элементы последовательно сравниваются попарно и, если порядок
в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до
тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что
означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на
своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и
название алгоритма.
Для
понимания и реализации этот алгоритм — простейший, но эффективен он лишь
для небольших массивов. Сложность алгоритма: O(n²).
При первом проходе
вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
·
если встречается более "легкий" (с меньшим значением)
элемент, то они меняются местами;
·
при встрече с более "тяжелым" элементом, последний
становится "эталоном" для сравнения, и все следующие
сравниваются с ним .
В результате наибольший
элемент оказывается в самом верху массива.
Псевдокод.
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1 FOR J=1 TO N-1 STEP 1
ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1 FOR I=1 TO N-J STEP 1
ЕСЛИ A[I]>A[I+1] ТО ОБМЕН A[I],A[I+1] IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]
СЛЕДУЮЩЕЕ I NEXT I
СЛЕДУЮЩЕЕ
J NEXT J
