Сортировка пузырьком - Алгоритмика
Сортировка пузырьком

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

Наш первый подход будет заключаться в следующем: обозначим за $n$ длину массива и $n$ раз пройдёмся раз пройдемся по нему слева направо, меняя два соседних элемента, если первый больше второго.

Каждую итерацию максимальный элемент «всплывает» как пузырек к концу массива — отсюда и название.

void bubble_sort(int *a, int n) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n - 1; i++)
            // сравниваем элемент со следующим
            if (a[i] > a[i + 1])
                // меняем местами, если следующий меньше
                swap(a[i], a[i + 1]);
}

int a[5] = {5, 2, 1, 3, 1};

bubble_sort(a, 5);

for (int i = 0; i < 5; i++)
    cout << a[i] << " ";

Корректность. По индукции можно показать, что после $k$ шагов алгоритма сортировки пузырьком последние $k$ чисел всегда отсортированы, а значит алгоритм работает корректно.

Асимптотика. Так как у нас два вложенных цикла, каждый из которых делает не более $O(n)$ итераций, внутри которых за $O(1)$ происходит сравнение и swap, суммарное время работы будет не более $O(n^2)$.

Упражнение. Алгоритм можно немного (неасимптотически) ускорить. Как нужно изменить границы в двух for-циклах, чтобы не делать никаких лишних действий?