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

Сортировка пузырьком — это простой алгоритм сортировки, который последовательно сравнивает соседние элементы массива и меняет их местами, если они находятся в неправильном порядке. Процесс повторяется до тех пор, пока массив не будет полностью отсортирован.

Алгоритм:

1. Проходим по массиву, сравнивая каждую пару соседних элементов.
2. Если текущий элемент больше следующего, меняем их местами.
3. Повторяем процесс для всех элементов, пока не пройдем весь массив без перестановок.

Пример на Java:

public 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; // если перестановок не было, массив отсортирован
    }
}

Сложность:

• В худшем случае: O(n²)
• В лучшем случае (уже отсортированный массив): O(n) с оптимизацией
• Потребление памяти: O(1) (in-place)