Как работает сортировка пузырьком?

Сортировка пузырьком: полный разбор

Сортировка пузырьком (Bubble Sort) — это один из самых простых алгоритмов сортировки. Хотя он неэффективен для больших объёмов данных, он идеален для понимания основ и часто встречается на собеседованиях.

Принцип работы

Основная идея: алгоритм многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Больший элемент как бы «всплывает» (bubble) к концу массива с каждой итерацией.

Шаги алгоритма

1. Начинаем с первого элемента массива
2. Сравниваем текущий элемент со следующим
3. Если текущий больше следующего, меняем их местами
4. Переходим к следующей паре элементов
5. Повторяем процесс до конца массива (первый проход)
6. После каждого прохода наибольший элемент занимает свою позицию в конце
7. Повторяем все проходы, уменьшая диапазон сортировки на один элемент

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

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        
        // Внешний цикл для количества проходов
        for (int i = 0; i < n - 1; i++) {
            // Внутренний цикл для сравнения соседних элементов
            for (int j = 0; j < n - 1 - i; j++) {
                // Сравниваем соседние элементы
                if (arr[j] > arr[j + 1]) {
                    // Меняем их местами
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr)); // [11, 12, 22, 25, 34, 64, 90]
    }
}

Оптимизированная версия

Можно добавить флаг, который указывает, были ли произведены какие-либо обмены. Если в проходе обмены не произошли, массив уже отсортирован:

public static void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Обмен элементов
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // Если обменов не было, массив отсортирован
        if (!swapped) break;
    }
}

Сложность и характеристики

• Временная сложность:

  • Худший случай: O(n²) — когда массив отсортирован в обратном порядке
  • Лучший случай: O(n) — когда массив уже отсортирован (оптимизированная версия)
  • Средний случай: O(n²)

• Пространственная сложность: O(1) — сортируем на месте, дополнительная память не требуется

• Стабильность: Да — относительный порядок равных элементов сохраняется

• Адаптивность: Да — оптимизированная версия быстрее работает на почти отсортированных массивах

Пример пошагового выполнения

Для массива [5, 2, 8, 1, 9]:

Проход 1:

• Сравниваем 5 и 2 → меняем → [2, 5, 8, 1, 9]
• Сравниваем 5 и 8 → не меняем → [2, 5, 8, 1, 9]
• Сравниваем 8 и 1 → меняем → [2, 5, 1, 8, 9]
• Сравниваем 8 и 9 → не меняем → [2, 5, 1, 8, 9] (9 на месте)

Проход 2:

• [2, 5, 1, 8, 9] → [2, 1, 5, 8, 9] (8 на месте)

Проход 3:

• [2, 1, 5, 8, 9] → [1, 2, 5, 8, 9] (5 на месте)

Проход 4:

• [1, 2, 5, 8, 9] — уже отсортирован

Когда использовать

• Образование: отлично для обучения основам алгоритмов
• Малые массивы: приемлем для массивов с < 10 элементами
• Почти отсортированные данные: оптимизированная версия хороша для частично отсортированных данных

Когда НЕ использовать

• Большие массивы (> 1000 элементов)
• Production-код, требующий высокой производительности
• Вместо этого используй QuickSort, MergeSort или встроенные методы сортировки

Сравнение с другими алгоритмами

Для Java обычно используют Arrays.sort(), который применяет Dual-Pivot QuickSort (O(n log n) в среднем случае), а не bubble sort.

Bubble Sort остаётся важным алгоритмом для понимания базовых концепций сортировки и часто используется как первый пример при обучении структурам данных и алгоритмам.