Почему большие числа оказываются в конце
Пузырьковая сортировка не ищет место для каждого числа отдельно. Она проходит по списку слева направо и сравнивает соседние элементы. Если пара стоит в неправильном порядке, элементы меняются местами. Поэтому крупное число при каждой такой встрече сдвигается на одну позицию вправо — как пузырёк, который постепенно поднимается к поверхности.
После одного прохода наибольшее число уже оказывается в конце списка. Этот участок можно больше не проверять: следующий проход найдёт место для второго по величине числа, затем для третьего. Алгоритм продолжает проходы, пока список не будет упорядочен. В некоторых вариантах он останавливается раньше, если за целый проход не произошло ни одной перестановки: значит, соседние пары уже стоят правильно.
Простота, за которую приходится платить
Каждый проход проверяет много пар, а проходов может понадобиться почти столько же, сколько элементов в списке. В результате при увеличении списка вдвое число сравнений растёт примерно в четыре раза. Это квадратичная сложность — так называют рост объёма работы пропорционально квадрату размера задачи.
Именно поэтому пузырьковая сортировка удобна для демонстрации, но обычно не подходит для больших наборов данных: алгоритмы вроде быстрой сортировки или сортировки слиянием справляются с ними значительно эффективнее. Зато её движение легко проследить вручную: за один проход на своё окончательное место гарантированно попадает максимальный элемент.
