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

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

Основные шаги:

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

Пример на Java:

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) (сортировка на месте).

Подходит для небольших массивов, но неэффективен для больших данных.