Сортировка пузырьком
Алгоритм сортировки — это алгоритм для упорядочивания элементов. Поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Сложность алгоритма: O(n²).
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Псевдокод
Вход: массив A, состоящий из элементов A[0], A[1], ..., A[n-1], который требуется отсортировать по возрастанию
цикл для i = 0, 1, ..., n − 1:
цикл для j = i + 1, ..., n − 2:
если A[j] > A[j+1], то:
обменять местами элементы A[j] и A[j+1]
Оптимизация
- Внутренний цикл можно выполнять для , где — номер итерации внешнего цикла, так как на -й итерации последние элементов массива уже будут правильно упорядочены.
- Внешний цикл можно заменить на цикл вида: пока произведится хотя бы один обмен на очередной итерации внешнего цикла, продолжать выполнение.
И тогда псевдокод будет выглядеть так:
t := истина
цикл пока t:
t := ложь
цикл для j = 0, 1, ..., n − 2:
если A[j] > A[j+1], то:
обменять местами элементы A[j] и A[j+1]
t := истина
Пример работы алгоритма
Возьмём массив с числами «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)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив отсортирован и алгоритм может быть завершён.
