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

Большие элементы всплывают вправо

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

static void bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;

        for (int i = 0; i < end; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            return;
        }
    }
}

Переменная end показывает правую границу ещё не отсортированной части. После каждого прохода её можно уменьшить: элемент на позиции end уже максимален среди оставшихся и больше не требует сравнений.

Зачем нужен флаг swapped

Если за полный проход не произошло ни одного обмена, массив уже отсортирован и дальнейшие проходы ничего не изменят. Благодаря этой проверке почти отсортированные данные иногда обрабатываются намного быстрее.

Сложность

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