Урок 9.2 — Пузырьковая сортировка (Bubble Sort)

Название «пузырёк» происходит от того, как элементы «всплывают» на свои места, как пузырьки воздуха в воде. Самые большие элементы постепенно смещаются в конец массива.

Алгоритм состоит из одного простого действия, которое повторяется много раз:

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

После первого прохода мы знаем, что последний элемент уже на своём месте. Поэтому следующий проход делаем на один элемент короче. И так далее, пока весь массив не станет отсортированным.

Рассмотрим массив [5, 3, 8, 1, 2]. Отсортируем его по возрастанию Bubble Sort.

Проход 1 (i = 0):

[5, 3, 8, 1, 2]  →  5 > 3? Да! Меняем  →  [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  →  5 > 8? Нет           →  [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  →  8 > 1? Да! Меняем  →  [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2]  →  8 > 2? Да! Меняем  →  [3, 5, 1, 2, 8]  ✓ 8 на месте

Проход 2 (i = 1) — последний элемент уже не трогаем:

[3, 5, 1, 2, 8]  →  3 > 5? Нет           →  [3, 5, 1, 2, 8]
[3, 5, 1, 2, 8]  →  5 > 1? Да! Меняем  →  [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8]  →  5 > 2? Да! Меняем  →  [3, 1, 2, 5, 8]  ✓ 5 на месте

Проход 3 (i = 2):

[3, 1, 2, 5, 8]  →  3 > 1? Да! Меняем  →  [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8]  →  3 > 2? Да! Меняем  →  [1, 2, 3, 5, 8]  ✓ 3 на месте

Проход 4 (i = 3):

[1, 2, 3, 5, 8]  →  1 > 2? Нет           →  [1, 2, 3, 5, 8]  ✓ Отсортировано!

Обрати внимание: после каждого прохода самый большой из оставшихся элементов оказывается в конце. Как пузырёк, который всплывает на поверхность. После n-1 проходов массив гарантированно отсортирован.

Напишем базовую реализацию Bubble Sort на C#. Она будет сортировать массив int[] по возрастанию.

static void BubbleSort(int[] arr)
{
    int n = arr.Length;

    // Внешний цикл — количество проходов
    for (int i = 0; i < n - 1; i++)
    {
        // Внутренний цикл — сравнение соседних элементов
        // n - 1 - i: с каждым проходом «всплывших» элементов становится больше
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])  // если левый больше правого
            {
                // Меняем местами
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Разберём код по строкам:

• Внешний цикл for (int i = 0; i < n - 1; i++) — выполняет n-1 проходов. i — номер прохода (начиная с 0).
• Внутренний цикл for (int j = 0; j < n - 1 - i; j++) — проходит по ещё неотсортированной части. n - 1 - i — потому что последние i элементов уже на своих местах.
• Сравнение и обмен — если arr[j] > arr[j+1], меняем их через временную переменную temp.

Полная программа с демонстрацией:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));

        BubbleSort(arr);

        Console.WriteLine("Отсортированный: " + string.Join(", ", arr));
    }

    static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }

            // Отладочный вывод после каждого прохода
            Console.WriteLine($"Проход {i + 1}: {string.Join(", ", arr)}");
        }
    }
}

// Вывод:
// Исходный массив: 64, 34, 25, 12, 22, 11, 90
// Проход 1: 34, 25, 12, 22, 11, 64, 90
// Проход 2: 25, 12, 22, 11, 34, 64, 90
// Проход 3: 12, 22, 11, 25, 34, 64, 90
// Проход 4: 12, 11, 22, 25, 34, 64, 90
// Проход 5: 11, 12, 22, 25, 34, 64, 90
// Проход 6: 11, 12, 22, 25, 34, 64, 90
// Отсортированный: 11, 12, 22, 25, 34, 64, 90

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

Добавим булевый флаг swapped:

static void OptimizedBubbleSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;  // флаг — были ли обмены в этом проходе

        for (int j = 0; j < n - 1 - i; 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;  // досрочный выход
    }
}

Сравни работу двух версий на почти отсортированном массиве:

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

// Базовая версия: сделает 4 прохода (всегда)
// Оптимизированная:
// Проход 1: [2, 3, 1, 4, 5] — была 1 замена
// Проход 2: [2, 1, 3, 4, 5] — была 1 замена
// Проход 3: [1, 2, 3, 4, 5] — была 1 замена
// Проход 4: swapped = false → break!  // досрочный выход!

Можно добавить ещё одну оптимизацию: запоминать позицию последнего обмена. После этой позиции массив уже отсортирован, и там проверять нечего:

static void DoubleOptimizedBubbleSort(int[] arr)
{
    int n = arr.Length;
    int lastSwap = n - 1;

    while (lastSwap > 0)
    {
        int currentLast = 0;  // последняя позиция, где был обмен

        for (int j = 0; j < lastSwap; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                currentLast = j;  // запомнили позицию обмена
            }
        }

        lastSwap = currentLast;  // дальше этой позиции ничего не проверяем
    }
}

Такой подход автоматически сокращает диапазон проверки на каждом проходе, причём иногда — больше чем на 1 элемент.

Bubble Sort — это отличный учебный инструмент, но в реальном коде используй встроенный Introsort или Merge Sort.

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

// Старый способ с temp
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

// Новый способ с кортежем (C# 7+)
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);

Компилятор C# сам создаст временную переменную. Код становится компактнее без потери производительности. Используй этот способ в современных проектах.

Проверь понимание Bubble Sort.