сортировка пузырьком

EN: bubble sort

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