Сортировка пузырьком
Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более проходов, где размер массива, чтобы отсортировать массив.
Псевдокод
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив , состоящий из элементов.
BubbleSort(A)
for i = 0 to n - 2
for j = 0 to n - 2
if A[j] > A[j + 1]
swap(A[j], A[j + 1]);
Оптимизация
- Можно заметить, что после -ой итерации внешнего цикла последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до , а до .
- Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не раз, а до тех пор, пока во внутреннем цикле происходят обмены.
Тогда сортировка примет такой вид:
BubbleSort(A)
i = 0;
t = true;
while t == true
t = false;
for j = 0 to n - i - 2
if A[j] > A[j + 1]
swap(A[j], A[j + 1]);
t = true;
i = i + 1;
Пример работы алгоритма
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
| До | После | Описание шага |
|---|---|---|
| 5 1 4 2 8 | 1 5 4 2 8 | Здесь алгоритм сравнивает два первых элемента и меняет их местами. |
| 1 5 4 2 8 | 1 4 5 2 8 | Меняет местами, так как 5 > 4 |
| 1 4 5 2 8 | 1 4 2 5 8 | Меняет местами, так как 5 > 2 |
| 1 4 2 5 8 | 1 4 2 5 8 | Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами. |
Второй проход:
| До | После | Описание шага |
|---|---|---|
| 1 4 2 5 8 | 1 4 2 5 8 | |
| 1 4 2 5 8 | 1 2 4 5 8 | Меняет местами, так как 4 > 2 |
| 1 2 4 5 8 | 1 2 4 5 8 | |
| 1 2 4 5 8 | 1 2 4 5 8 |
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще 2 прохода, на которых ничего не изменится.
