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

Интерактивная анимация

Это первая часть проекта. Далее будут сортировка выбором, гномья сортировка («глупая»), сортировка вставками, сортировка Шелла, слиянием, кучей и сортировка Хоара (быстрая).

Сортировка пузырьком известна многим. Её идея очень проста: берём пары соседних элементов и меняем их местами, если порядок неверный. И так много раз.

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

Эта страница содержит интерактивный элемент, который не может быть отображён. Пожалуйста, посетите страницу.

Разберём некоторые детали. Внешний цикл задаёт количество проходов.

for (i = 0; i < size - 1; ++i)

Покажем, что условие i < size - 1 оптимально. Возьмём массив, элементы которого изначально отсортированы по убыванию (худший случай).

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10 // После 1-го прохода.
8 7 6 5 4 3 2 1 9 10 // После 2-го прохода.
7 6 5 4 3 2 1 8 9 10 // После 3-го прохода.
6 5 4 3 2 1 7 8 9 10 // После 4-го прохода.
5 4 3 2 1 6 7 8 9 10 // После 5-го прохода.
4 3 2 1 5 6 7 8 9 10 // После 6-го прохода.
3 2 1 4 5 6 7 8 9 10 // После 7-го прохода.
2 1 3 4 5 6 7 8 9 10 // После 8-го прохода.
1 2 3 4 5 6 7 8 9 10 // После 9-го прохода.

Для десяти элементов понадобилось девять проходов.

Внутренний цикл занимается тем, что перебирает пары и меняет элементы местами (при необходимости).

for (j = 0; j < size - i - 1; ++j)

Эта строка могла бы выглядеть иначе (что часто можно встретить):

for (j = 0; j < size - 1; ++j)

Но почему мы остановились на первом варианте? Ответ кроется в названии сортировки. Пузырьковой она называется потому, что самый большой элемент «всплывает» наверх на каждом этапе (после первого прохода 10 окажется в конце). Поэтому на каждом новом проходе нужно сортировать всё меньше элементов.

6 ноября 2017 · программирование · сортировки