Как работает сортировка пузырьком? Какова её сложность?

Сортировка пузырьком многократно сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода наибольший элемент «всплывает» в конец списка; средняя и худшая временная сложность алгоритма — O(n²).