bulgakov

36. Сортировка: пузырьковый метод

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

Что пригодится из прошлого: массивы, условие if, цикл do…while, цикл for. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Что значит «отсортировать»

Дан массив из семи целых чисел:

44  21  26  6  192  5  -6

Сортировка по возрастанию расставляет их от меньшего к большему:

-6  5  6  21  26  44  192

Сортировка по убыванию — от большего к меньшему:

192  44  26  21  6  5  -6

Результат остаётся тем же массивом. Меняются только места элементов; новых значений не появляется.

Идея пузырькового метода

Метод состоит из двух шагов (сортировка по возрастанию):

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

Один просмотр массива слева направо называется проходом. Большие числа при проходе «всплывают» к концу, как пузырьки воздуха к поверхности, отсюда название.

Разбор на маленьком массиве

Возьмём массив 5 3 8 4 6 и пройдём по нему. На каждом шаге сравниваем пару соседей.

Проход 1.

Сравниваем Что делаем Массив после шага
5 и 3 5 > 3 — меняем 3 5 8 4 6
5 и 8 5 < 8 — оставляем 3 5 8 4 6
8 и 4 8 > 4 — меняем 3 5 4 8 6
8 и 6 8 > 6 — меняем 3 5 4 6 8

Замены были, значит нужен ещё проход. Но самое важное уже случилось: наибольшее число 8 оказалось на последнем месте. Оно «всплыло» и дальше двигаться не будет.

Проход 2. Снова идём с начала массива.

Сравниваем Что делаем Массив после шага
3 и 5 3 < 5 — оставляем 3 5 4 6 8
5 и 4 5 > 4 — меняем 3 4 5 6 8
5 и 6 5 < 6 — оставляем 3 4 5 6 8
6 и 8 6 < 8 — оставляем 3 4 5 6 8

Теперь на своём месте и второе по величине число 6. Замена была, поэтому нужен ещё проход.

Проход 3. Идём ещё раз: 3 < 4, 4 < 5, 5 < 6, 6 < 8. Замен не было — алгоритм заканчивается. Массив отсортирован: 3 4 5 6 8.

Всё движение одной картинкой: состояние после каждого прохода. Чертой отмечена граница: справа от неё числа уже точно стоят на своих местах:

начало:     5  3  8  4  6
проход 1:   3  5  4  6 │ 8        8 всплыла в конец
проход 2:   3  4  5 │ 6  8        6 заняла своё место
проход 3:   3  4 │ 5  6  8        замен нет — готово

Заметьте, что последний проход ничего не меняет. Он нужен, чтобы убедиться, что порядок уже правильный.

Как поменять два значения местами

Основное действие метода — обмен двух элементов. Новички пишут так:

C
#include <stdio.h>

int main(void)
{
    int a = 5;
    int b = 3;

    a = b;
    b = a;
    printf("a = %d, b = %d\n", a, b);
    return 0;
}

Вывод:

a = 3, b = 3

Ожидали a = 3, b = 5, а получили обе тройки. Причина в порядке действий. После a = b; старое значение a (число 5) затёрто. Следующая строка b = a; копирует уже новое a, то есть тройку. Пятёрка потеряна.

Правильно использовать третью переменную, в которой временно хранится первое значение:

C
#include <stdio.h>

int main(void)
{
    int a = 5;
    int b = 3;

    int temp = a;
    a = b;
    b = temp;
    printf("a = %d, b = %d\n", a, b);
    return 0;
}

Вывод:

a = 3, b = 5

Здесь temp сохраняет пятёрку до того, как a перезаписывается. Затем a получает значение b, и b получает сохранённое в temp. Это как переставить содержимое двух стаканов: без третьего пустого стакана не обойтись. Шаги по очереди:

Шаг Действие a b temp
начало — 5 3 не задана
1 temp = a; 5 3 5
2 a = b; 3 3 5
3 b = temp; 3 5 5

На шаге 2 в a и b стоят две тройки, но пятёрка не потеряна: она лежит в temp. В сортировке роль a и b играют arr[i] и arr[i + 1].

Программа: простая версия

Отсортируем массив из первого примера. Полная программа:

C
#include <stdio.h>

int main(void)
{
    int size = 7;
    int arr[] = {44, 21, 26, 6, 192, 5, -6};
    int swapped = 0;

    do {
        swapped = 0;
        for (int i = 0; i < size - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = 1;
            }
        }
    } while (swapped);

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

Вывод:

-6 5 6 21 26 44 192 

Здесь два цикла, и важно не путать их роли. Внешний (do … while) — это проходы: он повторяется, пока есть замены. Внутренний (for) — один проход: он перебирает пары соседей слева направо. Размер size мы записали числом для наглядности; его можно вычислить и через sizeof(arr) / sizeof(arr[0]), как в уроке про массивы.

Разберём части.

  • int arr[] = {...} — массив, а size хранит число его элементов (7).
  • swapped — флаг: «в этом проходе была хотя бы одна замена». Перед каждым проходом он сбрасывается в 0. Замена записывает 1.
  • do { ... } while (swapped); повторяет проходы, пока замены происходят. Цикл do…while выполняется минимум один раз, а проверка стоит в конце (урок про do…while).
  • for (int i = 0; i < size - 1; i++) — один проход. Сравниваются arr[i] и arr[i + 1]. Последний допустимый индекс i + 1 равен size - 1, поэтому i доходит только до size - 2. Условие i < size - 1 это обеспечивает. Было бы i < size, на последнем шаге программа обратилась бы к arr[size] за границей массива.
  • Внутри if — обмен через temp и запись swapped = 1.

Чтобы увидеть проходы, добавим печать массива после каждого. Полная программа для 5 3 8 4 6:

C
#include <stdio.h>

int main(void)
{
    int size = 5;
    int arr[] = {5, 3, 8, 4, 6};
    int swapped = 0;
    int pass = 0;

    do {
        swapped = 0;
        for (int i = 0; i < size - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = 1;
            }
        }
        pass++;
        printf("after pass %d:", pass);
        for (int i = 0; i < size; i++) {
            printf(" %d", arr[i]);
        }
        printf("  swapped = %d\n", swapped);
    } while (swapped);
    return 0;
}

Вывод:

after pass 1: 3 5 4 6 8  swapped = 1
after pass 2: 3 4 5 6 8  swapped = 1
after pass 3: 3 4 5 6 8  swapped = 0

Совпадает с разбором выше: три прохода, на последнем замен нет.

Улучшение: не трогать уже готовый хвост

Заметьте, что в простой версии каждый проход заново сравнивает и те элементы, которые уже на своих местах. Причина в том, что после k-го прохода на своих местах оказываются k последних элементов. Значит, проход можно заканчивать раньше.

Для этого заведём границу compareUntil. Она показывает, сколько элементов с начала ещё нужно проверять. В начале это size, после каждого прохода она уменьшается на единицу:

C
#include <stdio.h>

int main(void)
{
    int size = 8;
    int arr[] = {5, 3, 8, 4, 6, -1, 0, 100};
    int swapped = 0;
    int compareUntil = size;

    do {
        swapped = 0;
        for (int i = 0; i < compareUntil - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = 1;
            }
        }
        compareUntil--;
    } while (swapped);

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

Вывод:

-1 0 3 4 5 6 8 100 

В заголовке прохода вместо size - 1 теперь compareUntil - 1. Посмотрим, как меняется граница для первых проходов массива из восьми элементов:

Проход compareUntil Сравниваются пары с индексами Закреплено в конце
1 8 от 0 до 6 arr[7]
2 7 от 0 до 5 arr[6], arr[7]
3 6 от 0 до 4 arr[5]…arr[7]

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

проход 1 (compareUntil = 8):   5  3  8  4  6  -1  0  100
проход 2 (compareUntil = 7):   3  5  4  6  -1  0  8 │ 100
проход 3 (compareUntil = 6):   3  4  5  -1  0  6 │ 8  100

Результат тот же, а число сравнений меньше. На сколько именно, посчитаем в уроке про сложность.

Сортировка по убыванию

Чтобы сортировать по убыванию, достаточно поменять одно условие: обмен делаем, когда первый меньше второго:

C
#include <stdio.h>

int main(void)
{
    int size = 7;
    int arr[] = {44, 21, 26, 6, 192, 5, -6};
    int swapped = 0;

    do {
        swapped = 0;
        for (int i = 0; i < size - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = 1;
            }
        }
    } while (swapped);

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

Вывод:

192 44 26 21 6 5 -6 

Единственное изменение — знак < вместо > в if (arr[i] < arr[i + 1]). Теперь наименьшие значения «всплывают» к концу, а наибольшие собираются в начале.

Видео с анимацией этого метода (на английском) — Bubble Sort Algorithm. Когда таблицы выше станут понятны, посмотрите, как те же обмены выглядят в движении.

Что запомнить

  • Пузырёк сравнивает соседей и меняет их местами, если они стоят в неправильном порядке; проходы повторяются, пока есть замены.
  • Обмен двух значений делается через третью переменную.
  • Граница прохода i < size - 1: сравниваем arr[i] и arr[i + 1].
  • После k-го прохода k последних элементов уже на своих местах, поэтому проход можно укорачивать.
  • Для сортировки по убыванию меняем знак сравнения.
ПрактикаЗагружаем тест…