Сортировка пузырьком на языке C: как работает, код и сложность

Сортировка пузырьком (bubble sort) — это простой алгоритм упорядочивания массива, в котором соседние элементы сравниваются попарно и меняются местами, если стоят в неправильном порядке. За несколько проходов по массиву самые большие значения постепенно «всплывают» к его концу, как пузырьки воздуха в воде — отсюда и название.

Ниже — как алгоритм работает по шагам (проходы и обмены), полный код на языке C с разбором, оценка сложности O(n^2), оптимизация ранним выходом по флагу и разбор того, когда пузырьковую сортировку стоит применять, а когда нет. Весь код — законченные программы на C, вывод которых сверен с реальным.

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

Идея простая. Алгоритм проходит по массиву слева направо и на каждом шаге сравнивает пару соседних элементов. Если левый больше правого, элементы меняются местами. За один такой проход самый большой из еще неупорядоченных элементов гарантированно доходит до своего места в конце.

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

Прогоним алгоритм руками на массиве [5, 1, 4, 2, 8], чтобы увидеть состояние на каждом шаге.

Проход 1 (сравниваем все соседние пары):

• [5, 1, 4, 2, 8] — 5 > 1, меняем -> [1, 5, 4, 2, 8]
• [1, 5, 4, 2, 8] — 5 > 4, меняем -> [1, 4, 5, 2, 8]
• [1, 4, 5, 2, 8] — 5 > 2, меняем -> [1, 4, 2, 5, 8]
• [1, 4, 2, 5, 8] — 5 < 8, не меняем -> [1, 4, 2, 5, 8]

После первого прохода наибольшее число 8 встало на свое место в конце.

Проход 2 (последний элемент уже на месте, его можно не трогать):

• [1, 4, 2, 5, 8] — 1 < 4, не меняем
• [1, 4, 2, 5, 8] — 4 > 2, меняем -> [1, 2, 4, 5, 8]
• [1, 2, 4, 5, 8] — 4 < 5, не меняем

Теперь на своих местах два наибольших числа — 5 и 8.

Проход 3:

• [1, 2, 4, 5, 8] — 1 < 2, не меняем
• [1, 2, 4, 5, 8] — 2 < 4, не меняем

За весь проход не случилось ни одного обмена — значит, массив уже упорядочен и работу можно прекратить. Итог: [1, 2, 4, 5, 8].

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

Вот та же логика в виде законченной программы на C. Массив задан прямо в коде, чтобы пример можно было скопировать и запустить без ввода с клавиатуры.

#include <stdio.h>

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    int n = sizeof(a) / sizeof(a[0]);   // число элементов массива

    for (int i = 0; i < n - 1; i++) {           // всего до n-1 проходов
        for (int j = 0; j < n - 1 - i; j++) {   // с каждым проходом хвост уже отсортирован
            if (a[j] > a[j + 1]) {              // левый больше правого - меняем местами
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Программа выведет отсортированный массив:

1 2 4 5 8 

Разберем ключевые места:

• n = sizeof(a) / sizeof(a[0]) считает число элементов: общий размер массива в байтах делим на размер одного элемента. Так длину не приходится писать вручную.
• Внешний цикл по i задает проходы. Их достаточно n - 1: после каждого прохода как минимум один элемент встает на место.
• Внутренний цикл по j идет до границы n - 1 - i. Уменьшение верхней границы на i — та самая оптимизация из ручного прогона: хвост массива уже отсортирован, повторно сравнивать его не нужно.
• Обмен делается через временную переменную tmp: без нее присваивание a[j] = a[j + 1] затерло бы одно из значений.

Частая ошибка: выход за границу массива

Внутри цикла мы обращаемся к a[j + 1], поэтому j не должен доходить до последнего индекса. Если по невнимательности написать условие с выходом за край:

for (int j = 0; j <= n - 1; j++) {   // ошибка: при j = n-1 читаем a[n]
    if (a[j] > a[j + 1]) { /* ... */ }
}

то на последней итерации j станет равным n - 1, а a[j + 1] обратится к a[n] — за пределы массива. В C это неопределенное поведение: программа может напечатать мусорное число, отработать «как будто нормально» или аварийно завершиться — конкретный исход зависит от компилятора, флагов и содержимого памяти. Инструмент AddressSanitizer (-fsanitize=address) ловит такой доступ и показывает heap-buffer-overflow или stack-buffer-overflow.

Правильная верхняя граница — строго меньше n - 1 (а с учетом оптимизации n - 1 - i), тогда a[j + 1] всегда остается внутри массива.

Сложность сортировки пузырьком: O(n^2)

Оценим, сколько сравнений делает алгоритм. На массиве из n элементов первый проход выполняет n - 1 сравнение, второй — n - 2 и так далее. Сумма (n - 1) + (n - 2) + ... + 1 равна n * (n - 1) / 2.

Для нашего примера с n = 5 это 5 * 4 / 2 = 10 сравнений. При росте n слагаемое n^2 / 2 растет быстрее всего, а константы и младшие члены отбрасываются — получаем O(n^2).

Важная оговорка: лучший случай O(n) достижим не сам по себе, а только если добавить ранний выход по флагу. В коде выше внешний цикл всегда прогоняется n - 1 раз независимо от данных, поэтому без флага даже уже отсортированный массив обойдется в O(n^2). По памяти алгоритм экономичен: сортировка идет на месте, дополнительной памяти нужно O(1).

Оптимизация: флаг swapped и ранний выход

Чтобы получить лучший случай O(n), заводят флаг swapped. Он показывает, был ли на текущем проходе хотя бы один обмен. Если за целый проход обменов не было, массив уже упорядочен и остальные проходы можно пропустить.

#include <stdio.h>

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    int n = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;                        // были ли обмены на этом проходе
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;                     // отметили, что обмен был
            }
        }
        if (swapped == 0) {                      // проход без обменов - все отсортировано
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Результат тот же:

1 2 4 5 8 

Разница не в выводе, а в числе проходов. На нашем массиве обмены прекращаются раньше, и цикл выходит по break, не доводя дело до формального n - 1 прохода. А если подать на вход уже отсортированный массив, первый же проход не сделает ни одного обмена — алгоритм завершится за один проход, то есть за O(n). Именно этот прием и превращает лучший случай в линейный.

Когда применять пузырьковую сортировку, а когда нет

Пузырьковая сортировка ценна прежде всего как учебный алгоритм: на ней удобно объяснять сравнения, обмены и оценку сложности. В реальном коде ее почти не используют.

Когда пузырек уместен:

• учеба и разбор основ алгоритмов, где важна наглядность, а не скорость;
• очень маленькие массивы (единицы элементов), где разница со сложными алгоритмами незаметна;
• почти отсортированные данные — с флагом swapped один проход подтвердит порядок за O(n).

Когда лучше выбрать другое:

• большие массивы — O(n^2) быстро становится неприемлемым; подойдут сортировки за O(n log n), например быстрая сортировка или сортировка слиянием;
• боевой код на C — как правило, берут стандартную функцию qsort из <stdlib.h>, а не пишут сортировку руками.

Пузырьковая сортировка устойчива: одинаковые элементы сохраняют исходный взаимный порядок, потому что обмен происходит только при строгом a[j] > a[j + 1].

FAQ

Почему алгоритм называется «пузырьковым»? Потому что большие элементы за каждый проход «всплывают» к концу массива, как пузырьки воздуха поднимаются к поверхности воды. За первый проход всплывает самый большой элемент, за второй — следующий по величине, и так далее.

Сортирует ли пузырек по убыванию? Да, достаточно поменять знак сравнения: вместо a[j] > a[j + 1] написать a[j] < a[j + 1]. Тогда наверх будут «всплывать» наименьшие элементы, и массив упорядочится по убыванию.

Чем пузырьковая сортировка отличается от сортировки выбором и вставками? Все три имеют сложность O(n^2), но работают по-разному: пузырек меняет местами соседние пары, сортировка выбором ищет минимум и ставит его в начало, а сортировка вставками вставляет очередной элемент в уже упорядоченную часть. На почти отсортированных данных вставки и пузырек с флагом ведут себя лучше сортировки выбором.

Выводы

• Сортировка пузырьком сравнивает соседние элементы и меняет их местами, пока за очередной проход не останется ни одного обмена.
• За каждый проход наибольший из неупорядоченных элементов встает на свое место в конце, поэтому верхнюю границу внутреннего цикла можно уменьшать (n - 1 - i).
• Сложность в худшем и среднем случае — O(n^2); лучший случай O(n) достижим только с флагом swapped и ранним выходом. Память — O(1), сортировка идет на месте.
• Обращение к a[j + 1] требует условия j < n - 1: иначе выход за границу массива дает неопределенное поведение.
• На практике это учебный алгоритм: для реальных задач на C берут qsort или сортировки за O(n log n).

Где применяется на практике

Пузырьковая сортировка — это первый шаг в теме алгоритмов сортировки и оценки сложности. Разобравшись с проходами, обменами и O(n^2), дальше логично идти к быстрым сортировкам, структурам данных и умению выбирать алгоритм под задачу — это база для любого разработчика.

Смежные темы: Массивы в программировании, Виды и характеристики алгоритмов, Циклы и их параметры.