Сортировка пузырьком
Сортировка пузырьком - это метод сортировки массивов и списков путем последовательного сравнения и обмена соседних элементов, если предшествующий оказывается больше последующего (при сортировке по возрастанию).
В процессе выполнения данного алгоритма элементы с большими значениями оказываются в конце списка, а элементы с меньшими значениями постепенно перемещаются по направлению к началу списка. Образно говоря, тяжелые элементы падают на дно, а легкие медленно всплывают подобно пузырькам воздуха. При этом в начале сортировки отсортированным становится конец списка, а не его начало.
В сортировке методом пузырька количество итераций внешнего цикла определяется длинной списка минус единица, так как когда второй элемент становится на свое место, то первый уже однозначно минимальный и не требует сортировки.
Количество итераций внутреннего цикла зависит от номера итерации внешнего цикла, так как конец списка уже отсортирован, и выполнять проход по этим элементам смысла нет.
Пусть имеется список из пяти элементов [6, 12, 4, 3, 8].
За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:
- 6 > 12? Нет
- 12 > 4? Да. Меняем местами
- 12 > 3? Да. Меняем местами
- 12 > 8? Да. Меняем местами
Результат: [6, 4, 3, 8, 12]
За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:
- 6 > 4? Да. Меняем местами
- 6 > 3? Да. Меняем местами
- 6 > 8? Нет
Результат: [4, 3, 6, 8, 12]
На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:
- 4 > 3? Да. Меняем местами
- 4 > 6? Нет
Результат: [3, 4, 6, 8, 12]
На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:
- 3 > 4? Нет
Результат: [3, 4, 6, 8, 12]
Реализация сортировки пузырьком на языке программирования Python с помощью циклов for
from random import randint N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) for i in range(N-1): for j in range(N-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] print(a)
Пример выполнения кода:
[63, 80, 62, 69, 71, 37, 12, 90, 19, 67] [12, 19, 37, 62, 63, 67, 69, 71, 80, 90]
С помощью циклов while
:
from random import randint N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) i = 0 while i < N - 1: j = 0 while j < N - 1 - i: if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] j += 1 i += 1 print(a)
Функция сортировки пузырьком на Python:
from random import randint def bubble(array): for i in range(N-1): for j in range(N-i-1): if array[j] > array[j+1]: buff = array[j] array[j] = array[j+1] array[j+1] = buff N = 10 a = [] for i in range(N): a.append(randint(1, 99)) print(a) bubble(a) print(a)