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, пока в проходе происходит хотя бы одна замена.
Один просмотр массива слева направо называется проходом. Большие числа при проходе «всплывают» к концу, как пузырьки воздуха к поверхности, отсюда название.
Разбор на маленьком массиве
Возьмём массив 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 замен нет — готово
Заметьте, что последний проход ничего не меняет. Он нужен, чтобы убедиться, что порядок уже правильный.
Как поменять два значения местами
Основное действие метода — обмен двух элементов. Новички пишут так:
#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, то есть тройку. Пятёрка потеряна.
Правильно использовать третью переменную, в которой временно хранится первое значение:
#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].
Программа: простая версия
Отсортируем массив из первого примера. Полная программа:
#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:
#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, после каждого прохода она уменьшается на единицу:
#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
Результат тот же, а число сравнений меньше. На сколько именно, посчитаем в уроке про сложность.
Сортировка по убыванию
Чтобы сортировать по убыванию, достаточно поменять одно условие: обмен делаем, когда первый меньше второго:
#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последних элементов уже на своих местах, поэтому проход можно укорачивать. - Для сортировки по убыванию меняем знак сравнения.
