Сортировка пузырьком
Интерактивная анимация

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

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

function bubbleSort(data, size)
{
for (i = 0; i < size - 1; ++i)
{
for (j = 0; j < size - i - 1; ++j)
{
if (data[j] > data[j + 1])
{
swap(data[j], data[j + 1]);
}
}
}
}

Шаг → Перезапуск Перезапуск (худший случай)

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

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
Сортировка выбором →
© MMXIMMXX. RSS
Светлая тема / тёмная тема