Пузырьковая сортировка на Python и C#

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

Содержание

Как работает алгоритм
Прогон по проходам на маленьком примере
Реализация на Python
Реализация на C
Сложность и когда применять
Выводы
Где применяется и что учить дальше
FAQ

Ниже разберем принцип на маленьком примере с прогоном по проходам вручную, затем напишем рабочий код на Python и C#, покажем частую ошибку с реальным сообщением и назовем границу применимости: где пузырьком пользоваться можно, а где нет.

Как работает алгоритм

Идея одна: за проход по массиву сравнивать каждую пару соседей слева направо и переставлять их, если левый больше правого. Тогда за один проход наибольший из оставшихся элементов гарантированно доедет до правого края.

Проговорим по шагам:

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

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

Прогон по проходам на маленьком примере

Возьмем массив [5, 1, 4, 2, 8] и отсортируем его по возрастанию. Отследим состояние после каждого прохода.

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

5 и 1 — меняем -> [1, 5, 4, 2, 8]
5 и 4 — меняем -> [1, 4, 5, 2, 8]
5 и 2 — меняем -> [1, 4, 2, 5, 8]
5 и 8 — не трогаем -> [1, 4, 2, 5, 8]

Итог прохода 1: [1, 4, 2, 5, 8], наибольший элемент 8 встал на место.

Проход 2 (правый край уже готов, до 8 не доходим):

1 и 4 — не трогаем
4 и 2 — меняем -> [1, 2, 4, 5, 8]
4 и 5 — не трогаем

Итог прохода 2: [1, 2, 4, 5, 8].

Проход 3: обменов нет ни в одной паре — значит массив отсортирован, останавливаемся. Финальный результат: [1, 2, 4, 5, 8].

Теперь формализуем этот же прогон в код.

Реализация на Python

Начнем с полной программы, которую можно скопировать и запустить целиком. Она сортирует тот же массив и печатает состояние после каждого прохода — удобно сверить с ручным прогоном выше.

def bubble_sort(arr):
    a = arr[:]                       # копия, чтобы не портить исходный список
    n = len(a)
    for i in range(n - 1):           # максимум n-1 проходов
        swapped = False
        for j in range(n - 1 - i):   # правый край уже отсортирован, туда не лезем
            if a[j] > a[j + 1]:      # соседи стоят не по порядку
                a[j], a[j + 1] = a[j + 1], a[j]  # меняем местами
                swapped = True
        print(f"после прохода {i + 1}: {a}")
        if not swapped:              # за проход не было обменов - список отсортирован
            break
    return a

data = [5, 1, 4, 2, 8]
print("исходный:", data)
print("результат:", bubble_sort(data))

Вывод программы:

исходный: [5, 1, 4, 2, 8]
после прохода 1: [1, 4, 2, 5, 8]
после прохода 2: [1, 2, 4, 5, 8]
после прохода 3: [1, 2, 4, 5, 8]
результат: [1, 2, 4, 5, 8]

Разберем ключевые места. Внешний цикл for i in range(n - 1) задает проходы, внутренний for j in range(n - 1 - i) идет по парам соседей. Вычитание - i каждый проход укорачивает внутренний цикл: правая часть массива уже упорядочена, повторно ее сравнивать незачем.

Флаг swapped включает досрочный выход. На третьем проходе обменов не было, swapped остался False, и цикл прервался через break. На уже отсортированном входе алгоритм отработает за один проход.

Обмен a[j], a[j + 1] = a[j + 1], a[j] — идиома Python: правая часть собирается в кортеж, потом распаковывается обратно, поэтому временная переменная не нужна.

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

Типичный промах новичка — пройти внутренним циклом до последнего индекса и обратиться к data[j + 1], которого уже нет.

data = [5, 1, 4, 2, 8]
n = len(data)
for j in range(n):                 # доходим до последнего индекса n-1
    if data[j] > data[j + 1]:      # data[j + 1] выходит за границу при j = n-1
        data[j], data[j + 1] = data[j + 1], data[j]
print(data)

Фактический результат — падение с исключением:

IndexError: list index out of range

Исправление: во внутреннем цикле идти до предпоследнего элемента, то есть range(n - 1) (а с учетом отсортированного хвоста — range(n - 1 - i), как в рабочем примере). Тогда data[j + 1] всегда существует.

Реализация на C

Та же логика на C#: функция BubbleSort принимает массив, сортирует его на месте и возвращает. Обмен записан через кортеж — синтаксис деконструкции доступен с C# 7.0.

using System;

class Program
{
    static int[] BubbleSort(int[] mas)
    {
        int n = mas.Length;
        for (int i = 0; i < n - 1; i++)             // максимум n-1 проходов
        {
            bool swapped = false;
            for (int j = 0; j < n - 1 - i; j++)     // правый край уже отсортирован
            {
                if (mas[j] > mas[j + 1])            // соседи не по порядку
                {
                    (mas[j], mas[j + 1]) = (mas[j + 1], mas[j]); // обмен кортежем
                    swapped = true;
                }
            }
            if (!swapped) break;                    // обменов не было - готово
        }
        return mas;
    }

    static void Main()
    {
        int[] data = { 5, 1, 4, 2, 8 };
        int[] sorted = BubbleSort(data);
        Console.WriteLine(string.Join(", ", sorted));
    }
}

Ожидаемый вывод в консоли:

1, 2, 4, 5, 8

Устройство то же, что и в Python: внешний цикл считает проходы, внутренний j < n - 1 - i бегает по парам и укорачивается с каждым проходом, флаг swapped дает досрочный выход. Отличается лишь синтаксис: типы указываются явно, а массив сортируется на месте, потому что в C# массив передается по ссылке.

Если нужен более старый компилятор без деконструкции кортежей, обмен пишут через временную переменную: int temp = mas[j]; mas[j] = mas[j + 1]; mas[j + 1] = temp;.

Сложность и когда применять

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

Случай	Число сравнений	Комментарий
Худший (обратный порядок)	порядка n в квадрате	O(n^2), каждая пара переставляется
Средний	порядка n в квадрате	O(n^2)
Лучший (уже отсортирован)	порядка n	O(n) за счет флага досрочного выхода

Дополнительной памяти алгоритм почти не требует (сортировка на месте), а относительный порядок равных элементов сохраняется — то есть сортировка устойчивая.

Практический вывод простой: на больших массивах квадратичное время делает пузырек непригодным. В реальном коде берут встроенные сортировки — list.sort() и sorted() в Python, Array.Sort() в C#: под капотом там алгоритмы со сложностью порядка n*log(n). Пузырьковая сортировка ценна как первый шаг в понимании того, как сортировка вообще устроена.

Выводы

Пузырьковая сортировка за каждый проход сравнивает соседние пары слева направо и меняет их местами, «всплывая» наибольший элемент к концу массива.
Флаг swapped дает досрочный выход: если за проход не было ни одного обмена, массив уже упорядочен и работу можно прекратить.
Внутренний цикл укорачивается с каждым проходом (n - 1 - i), потому что правый хвост массива уже отсортирован; выход внутреннего цикла за границу дает IndexError.
Сложность O(n^2) в худшем и среднем случае и O(n) в лучшем; сортировка устойчивая и на месте.
На практике пузырек не применяют из-за квадратичного времени: берут встроенные сортировки (list.sort()/sorted(), Array.Sort()) со сложностью порядка n*log(n); ценность пузырька учебная.

Где применяется и что учить дальше

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

Освойте тему на практике

Если хочется системно разобрать алгоритмы и структуры данных — с оценкой сложности, разными сортировками и практикой на реальных задачах — посмотрите курс Алгоритмы для разработчиков. Оценить формат и уровень до старта помогают бесплатные открытые уроки Otus — живые занятия с преподавателями.

Смежные темы: Сортировка: основные принципы, Сортировка массива на PHP.

FAQ

Почему внутренний цикл с каждым проходом становится короче? После i-го прохода i наибольших элементов уже стоят в конце на своих местах. Сравнивать их повторно незачем, поэтому граница n - 1 - i каждый раз сдвигается влево — это экономит лишние сравнения.

Пузырьковая сортировка устойчивая? Да. Обмен происходит только при строгом > (левый строго больше правого), поэтому равные элементы местами не меняются и их исходный относительный порядок сохраняется.

Чем пузырек отличается от сортировки выбором? Пузырек за проход многократно меняет соседей и «протаскивает» большой элемент к концу. Сортировка выбором за проход находит минимум (или максимум) и делает ровно один обмен, ставя его на нужное место. Обе квадратичные, но число обменов у выбора меньше.