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

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

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

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

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 окажется в конце). Поэтому на каждом новом проходе нужно сортировать всё меньше элементов.