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

Сортировка пузырьком (англ. bubble sort) — это простейший алгоритм сортировки, в котором соседние элементы массива попарно сравниваются и меняются местами, пока весь массив не станет упорядоченным. Это классическая учебная сортировка: её редко применяют на практике, но с неё удобно начинать знакомство с алгоритмами, и она регулярно встречается на собеседованиях.

Идея пузырьковой сортировки

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

Расположим массив сверху вниз, от нулевого элемента к последнему.

В результате нулевого прохода минимальный элемент «всплывает» вверх — отсюда и название алгоритма: сортировка пузырьком. Повторяем проход для всех элементов, кроме нулевого, — он уже находится на своём месте, — и находим второй наименьший элемент. Так продолжаем, пока весь массив не будет отсортирован.

Реализация на Java

Рассмотрим программу сортировки пузырьком на Java. Внешний цикл for отвечает за номер прохода, а внутренний — за перебор элементов в одном проходе. Обмен значений выполняется через временную переменную tmp. Во внутреннем цикле мы идём с конца массива (array.length - 1) и в каждом следующем проходе уменьшаем число просматриваемых элементов (условие j > i), потому что верхние позиции уже отсортированы.

public class BubbleSorter {
    public static void sort(int[] array) {
        // i - номер прохода
        for (int i = 0; i < array.length - 1; i++) {
            // внутренний цикл прохода
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
}

Проверка работы алгоритма

Будем вызывать метод BubbleSorter.sort() из класса BubbleSorterTest, приведённого ниже. Отсортируем каждую строку двумерного массива data:

import java.util.Arrays;

public class BubbleSorterTest {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            BubbleSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

Результат выполнения программы — слева исходный массив, справа отсортированный:

[] => []
[1] => [1]
[0, 3, 2, 1] => [0, 1, 2, 3]
[4, 3, 2, 1, 0] => [0, 1, 2, 3, 4]
[6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7] => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 123]

Оптимизация метода пузырька

У базового варианта есть недостаток: даже если массив уже отсортирован, алгоритм всё равно выполнит все проходы. Это легко исправить: заведём логический флаг swapped и будем сбрасывать его в начале каждого прохода. Если за целый проход не произошло ни одного обмена, значит массив уже упорядочен — и можно прервать сортировку досрочно.

public class OptimizedBubbleSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean swapped = false;
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                    swapped = true;
                }
            }
            // за проход не было обменов - массив отсортирован
            if (!swapped) {
                break;
            }
        }
    }
}

Благодаря флагу на уже отсортированном (или почти отсортированном) массиве алгоритм завершится за один проход. Это улучшает лучший случай с O(n²) до O(n), хотя худший и средний случаи остаются прежними.

Сложность алгоритма (Big O)

Пузырьковая сортировка выполняет вложенные проходы по массиву, поэтому в среднем и худшем случае число сравнений пропорционально n², где n — количество элементов.

Плюсы, минусы и когда использовать

Плюсы:

• очень простая реализация — легко понять и написать по памяти;
• сортирует «на месте», не требует дополнительной памяти (O(1));
• устойчива: одинаковые элементы не переставляются относительно друг друга;
• с оптимизацией флагом мгновенно определяет уже отсортированный массив.

Минусы:

• квадратичная сложность O(n²) — недопустимо медленно на больших массивах;
• делает много лишних обменов по сравнению, например, с сортировкой выбором.

Когда пузырьковую сортировку лучше не брать

На практике для реальных данных используйте встроенную сортировку Arrays.sort() (для примитивов это быстрая сортировка, для объектов — устойчивая TimSort) — она работает за O(n·log n). Метод пузырька уместен там, где массив совсем маленький или почти отсортирован, а также как учебный пример и задача на собеседовании. Для больших наборов данных выбирайте быструю сортировку, сортировку слиянием или пирамидальную сортировку.