Сортировка пузырьком

Сортировки   12 июля 2012  Автор статьи:  

Сортировка пузырьком — очень простой и соответственно малоэффективный алгоритм сортировки. Свое название алгоритм получил за так называемое «всплытие легких элементов», подобно пузырькам в воде. Отметим, что сортировка пузырьком является устойчивой, то есть сохраняет порядок следования равных элементов.
 
Описание алгоритма:
Пусть имеется последовательность А из n элементов, которую необходимо упорядочить по возрастанию (по убыванию) элементов. Нумерация элементов последовательности начинается с 0 и заканчивается n — 1.
Сортировка пузырьком состоит из следующих шагов:
1. Выбирается переменная-счетчик i = 0.
2. Если i >= n, то конец алгоритма.
3. Выбирается переменная-счетчик j = n — 1.
4. Проверяются соседние элементы a[j] и a[j-1]. Если a[j] меньше a[j — 1] (то есть элемент ниже, легче элемента выше), то элементы меняются местами (происходит «всплытие» более легкого элемента).
5. Уменьшается переменная-счетчик j на 1.
6. Если j > i, то повторяются шаги 4 — 5. В противном случае переменная-счетчик i увеличивается на 1 и повторяются шаги 2 — 5.
 
Иными словами алгоритм состоит из двух циклов: основного и вложенного.
Основной цикл совершает n итераций. А во вложенном цикле происходит n — i (где i — номер итерации основного цикла) итераций. Проверка элементов во вложенном цикле начинается с конца массива, и если находится элемент, который легче предыдущего, то они меняются местами. Таким образом на первой итерации основного цикла самый легкий элемент последовательности «всплывает» на первое место, на второй итерации самый легкий элемент (не учитывая первый) «всплывает» на второе место и так далее.
Замечание: если необходимо упорядочить последовательность по убыванию, то необходимо изменить проверку с меньше на больше, и производить «всплытие тяжелых элементов».
 
Пример работы алгоритма:
Пусть дана последовательность А из 5 элементов, необходимо упорядочить её по возрастанию:

1. Кладем счетчик i = 0.
2. i = 0 < 5 - правда. 3. Кладем счетчик j = 5 - 1 = 4. 4. Проверяем элементы a[4] и a[3]. a[4] < a[3] следовательно меняем их местами.
5. Уменьшаем j на 1. j = 3.
6. j = 3 > 0, следовательно повторяем шаги 4 — 5 алгоритма.
… Выполняем шаги 3 — 5 пока j > i …

7. j = 0 > 0 — ложь, следовательно увеличиваем i = 1 и выполняем шаги 2 — 5.
8. i = 1 < 5 - правда. 9. Кладем счетчик j = 5 - 1 = 4. 10. Проверяем элементы a[4] и a[3]. a[4] > a[3] следовательно замены не происходит.
11. Уменьшаем j на 1. j = 3.
12. j = 3 > 1, следовательно повторяем шаги 4 — 5 алгоритма.
13. Проверяем элементы a[3] и a[2]. a[3] < a[2] следовательно меняем их местами.
… и так далее, в результате получаем упорядоченную по возрастанию последовательность А …

Научиться программировать

  • на Delphi

  • на Java

  • на C++