Пузырьковая сорировка

Пузырьковая сортировка

Это учебная стабильная сортировка соседними обменами. После каждого полного прохода максимальный элемент неотсортированной части оказывается справа.

[5, 1, 4, 2]
 5↔1  -> [1, 5, 4, 2]
 5↔4  -> [1, 4, 5, 2]
 5↔2  -> [1, 4, 2, 5]  // 5 на окончательном месте

Java

static void bubbleSort(int[] values) {
    for (int last = values.length - 1; last > 0; last--) {
        boolean swapped = false;
 
        for (int i = 0; i < last; i++) {
            if (values[i] > values[i + 1]) {
                int tmp = values[i];
                values[i] = values[i + 1];
                values[i + 1] = tmp;
                swapped = true;
            }
        }
 
        if (!swapped) return;
    }
}

Инвариант внешнего цикла: диапазон (last, length) уже отсортирован и содержит крупнейшие элементы на финальных местах.

Сравнение строгое > сохраняет порядок равных элементов, поэтому алгоритм стабилен. Замена на >= нарушит стабильность.

Сложность

Случай	Время
уже отсортирован, с swapped	O(n)
средний	O(n²)
обратный порядок	O(n²)
память	O(1)

Без флага раннего выхода даже лучший случай остается O(n²). На практике для больших массивов алгоритм не используют: слишком много сравнений и обменов.

Edge cases

• пустой массив и один элемент — циклы не выполняются;
• все элементы равны — один проход;
• отрицательные числа не требуют отдельной логики.

На собеседовании

• Почему «пузырек» стабилен? Равные элементы не меняются местами при строгом >.
• Как получить O(n) best case? Прервать после прохода без обменов.
• Что верно после первого прохода? Максимум стоит в конце.
• Дополнительная память? O(1).