Как работает Bubble Sort?

# Bubble Sort: алгоритм и реализация

Bubble Sort (пузырьковая сортировка) — это простейший алгоритм сортировки, который работает путём многократного прохода по массиву и обмена соседних элементов, если они находятся в неправильном порядке. Каждый проход "всплывает" (bubble up) наибольший элемент в конец массива.

Основной принцип

Массив: [5, 3, 8, 1, 9]

Проход 1:
5 > 3? Да → обмен  → [3, 5, 8, 1, 9]
5 > 8? Нет           [3, 5, 8, 1, 9]
8 > 1? Да → обмен  → [3, 5, 1, 8, 9]
8 > 9? Нет           [3, 5, 1, 8, 9]
Результат: 9 "всплыло" в конец

Проход 2:
3 > 5? Нет           [3, 5, 1, 8, 9]
5 > 1? Да → обмен  → [3, 1, 5, 8, 9]
5 > 8? Нет           [3, 1, 5, 8, 9]
Результат: 8 на месте

Проход 3:
3 > 1? Да → обмен  → [1, 3, 5, 8, 9]
3 > 5? Нет           [1, 3, 5, 8, 9]
Результат: 5 на месте

Проход 4:
1 > 3? Нет           [1, 3, 5, 8, 9]
Результат: массив отсортирован!

Реализация на 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 - i - 1; 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 = {5, 3, 8, 1, 9};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));  // [1, 3, 5, 8, 9]
    }
}

Оптимизированная версия (Early Exit)

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

Сравнение: наихудший и лучший случаи

// Наихудший случай: [5, 4, 3, 2, 1]
Базовая версия: 10 операций (всегда n(n-1)/2)
Оптимизированная: 10 операций (не помогает)

// Лучший случай: [1, 2, 3, 4, 5]
Базовая версия: 10 операций (всё равно выполняет все циклы)
Оптимизированная: 4 операции (выходит после первого прохода)

Пошаговый пример

int[] arr = {3, 1, 4, 1, 5};

// Проход 1
Проход 0:     Операции
  i=0: 3 > 1? Да  → [1, 3, 4, 1, 5]
  j=1: 3 > 4? Нет → [1, 3, 4, 1, 5]
  j=2: 4 > 1? Да  → [1, 3, 1, 4, 5]
  j=3: 4 > 5? Нет → [1, 3, 1, 4, 5]  (5 "всплыла")

// Проход 2
Проход 1:     Операции
  i=0: 1 > 3? Нет → [1, 3, 1, 4, 5]
  j=1: 3 > 1? Да  → [1, 1, 3, 4, 5]
  j=2: 3 > 4? Нет → [1, 1, 3, 4, 5]  (4 на месте)

// Проход 3
Проход 2:     Операции
  i=0: 1 > 1? Нет → [1, 1, 3, 4, 5]
  j=1: 1 > 3? Нет → [1, 1, 3, 4, 5]  (3 на месте)

// Проход 4
Проход 3:     Операции
  i=0: 1 > 1? Нет → [1, 1, 3, 4, 5]  (готово)

С обобщёнными типами (Generics)

public class GenericBubbleSort {
    public static <T extends Comparable<T>> void bubbleSort(T[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // compareTo возвращает > 0 если this > other
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    // Обмен
                    T temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        // Работает с Integer
        Integer[] intArr = {5, 3, 8, 1, 9};
        bubbleSort(intArr);
        System.out.println(Arrays.toString(intArr));
        
        // Работает со String
        String[] strArr = {"dog", "cat", "apple", "zebra"};
        bubbleSort(strArr);
        System.out.println(Arrays.toString(strArr));
    }
}

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

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

Уход случай:         O(n²) — [n, n-1, ..., 2, 1]
Средний случай:      O(n²) — случайный массив
Лучший случай:       O(n)  — [1, 2, ..., n] (с оптимизацией)
С базовой версией:   O(n²) — всегда

Количество операций:
Базовая:    n(n-1)/2   = (n² - n) / 2
Оптимизир.: до n операций (если отсортирован)

Пространственная сложность

O(1) — in-place сортировка
       нужна только 1 переменная temp для обмена
       не требуется дополнительный массив

Таблица сложности

Почему Bubble Sort плохой?

// 1000 элементов
int[] arr = new int[1000];
BubbleSort.bubbleSort(arr);  // ≈ 500,000 операций

// QuickSort
Arrays.sort(arr);  // ≈ 10,000 операций

// Bubble Sort медленнее в 50 раз!

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

Когда Bubble Sort полезен?

✓ Образовательные цели (изучение алгоритмов)
✓ Почти отсортированные данные (с оптимизацией O(n))
✓ Очень маленькие массивы (< 50 элементов)
✓ Простые системы без требований производительности

✗ Production код
✗ Большие объёмы данных
✗ Критичная производительность

Практический совет

// ❌ Никогда не используй сам
BubbleSort.sort(arr);

// ✅ Используй встроённый Arrays.sort() — это Quick/Merge Sort
Arrays.sort(arr);

// ✅ Для объектов
Collections.sort(list);  // использует Timsort

Вывод

Bubble Sort — это важный алгоритм для обучения, но непригоден для production'а:

1. Простота — легко понять и реализовать
2. Доказательство — хорошая база для изучения сортировок
3. Неэффективность — O(n²) слишком медленно
4. Альтернативы — QuickSort (O(n log n)) или встроённые методы

Профессиональный совет: знай как работает для собеседования, но никогда не используй в коде. Используй Arrays.sort() и изучай более эффективные алгоритмы (QuickSort, MergeSort, HeapSort).