Сортировка пузырьком известна многим. Её идея очень проста: берём пары соседних элементов и меняем их местами, если порядок неверный. И так много раз.
Небольшое пояснение. Чтобы начать выполнение этого фрагмента кода, нажмите на первую кнопку. Выделяется та строка, которая будет выполнена следующей. В верхнем блоке для удобства отображаются значения некоторых переменных.
Шаг → Перезапуск Перезапуск (худший случай)
Разберём некоторые детали. Внешний цикл задаёт количество проходов.
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 окажется в конце). Поэтому на каждом новом проходе нужно сортировать всё меньше элементов.