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

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

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

Почему "пузырька"?

Алгоритм называется "пузырьковой сортировкой" потому, что большие элементы "всплывают" (bubble up) к концу массива подобно пузырькам воздуха, поднимающимся в воде. На каждом проходе наибольший элемент "поднимается" на свою финальную позицию.

Базовый алгоритм

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 - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Обмен элементов
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

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

Добавим флаг, чтобы остановиться, если на проходе не было обменов:

public class BubbleSortOptimized {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; 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;
            }
        }
    }
}

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

Для массива [64, 34, 25, 12, 22, 11, 90]:

Проход 1: Сравниваем соседние элементы и меняем их, если требуется:

• 64, 34 → 34, 64 (обмен)
• 64, 25 → 25, 64 (обмен)
• 64, 12 → 12, 64 (обмен)
• 64, 22 → 22, 64 (обмен)
• 64, 11 → 11, 64 (обмен)
• 64, 90 → 64, 90 (без обмена)

Результат: [34, 25, 12, 22, 11, 64, 90] — наибольший элемент на месте!

Проход 2: Самый большой элемент из оставшихся (64) занимает свою позицию и т.д.

Полная реализация с тестами

public class BubbleSortComplete {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; 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;
            }
        }
    }
    
    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]
    }
}

Анализ сложности

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

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

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

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

• Образовательные цели — для изучения основ алгоритмов
• Маленькие массивы — когда размер данных ≤ 10 элементов
• Частично отсортированные данные — с оптимизацией быстро завершается
• Практически НИКОГДА в production для больших данных

Альтернативы

Для реальных проектов используйте:

• Quick Sort — в среднем O(n log n)
• Merge Sort — гарантированно O(n log n)
• Heap Sort — O(n log n), сортирует на месте
• Arrays.sort() — встроенная оптимизированная сортировка Java