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

Введение

В данной статье познакомимся с сортировкой пузырьком, и реализуем её на Python.

Сортировка пузырьком — простой метод сортировки массивов, который последовательно сравнивает и обменивает соседние элементы, если предыдущий оказался больше последующего.

Алгоритм работы сортировки пузырьком

Допустим у нас есть следующий массив: [1, 5, 10, 2, 6, 4]

1. Значение первого элемента массива сравниваем со вторым. Если первый оказался больше второго, то они меняются местами, если нет — идём дальше:
   1 > 5 — Единица меньше пяти, поэтому идём дальше.
2. Берём значение второго элемента массива и сравниваем с третьим. Если второй больше третьего, то меняем их местами, если нет — идём дальше
   5 > 10 — Пять меньше десяти, поэтому идём дальше.
3. Повторяем всё те же действия, пока не кончится массив. В конце массива должен оказаться самый большой элемент.
   10 > 2 — Десять больше двух, меняем их местами
   10 > 6 — Десять больше шести, меняем их местами
   10 > 4 — Десять больше четырёх, меняем их местами
   Итог после первой итерации: [1, 5, 2, 6, 4, 10]
4. Переходим к следующей итерации, но в этот раз последний элемент затрагиваться не будет, т.к. в прошлой итерации было выявлено, что он самый большой.

Как менялся наш массив по итерациям:

1 итерация — [1, 5, 2, 6, 4, 10]
2 итерация — [1, 2, 5, 4, 6, 10]
3 итерация — [1, 2, 4, 5, 6, 10]
4 итерация — [1, 2, 4, 5, 6, 10]
5 итерация — [1, 2, 4, 5, 6, 10]
6 итерация — [1, 2, 4, 5, 6, 10]
7 итерация — [1, 2, 4, 5, 6, 10]

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

Для начала напишем генератор рандомного списка:

from random import randint
# Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100
array = [randint(1, 100) for i in range(10)]
print(array)

Определим количество элементов в списке:

from random import randint
# Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100
array = [randint(1, 100) for i in range(10)]
print(array)

length = len(array)

Создадим цикл, количество итераций в котором будет length-1:

from random import randint
# Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100
array = [randint(1, 100) for i in range(10)]
print(array)

length = len(array)

for i in range(length-1):

Внутри создадим вложенный цикл, у которого будет length-i-1 итераций:

from random import randint
# Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100
array = [randint(1, 100) for i in range(10)]
print(array)

length = len(array)

for i in range(length-1):
    for j in range(length-i-1):

Дальше будет идти условие, сравнивающее элемент массива со следующим элементом. Если же он больше, то они меняются местами, если нет — идёт следующая итерация:

from random import randint
# Заполняем список 10 рандомными элементами подбираемыми рандомно от 1, до 100
array = [randint(1, 100) for i in range(10)]
print(array)

length = len(array)

for i in range(length-1):
    for j in range(length-i-1):
        if array[j] > array[j+1]:
            b = array[j]
            array[j] = array[j+1]
            array[j+1] = b

print(array)

Вывод после запуска кода:

Начальный список — [71, 58, 30, 61, 95, 58, 100, 27, 46, 95]
Отсортированный список — [27, 30, 46, 58, 58, 61, 71, 95, 95, 100]

Заключение

В ходе статьи мы с Вами разобрались с тем, как работает сортировка пузырьком, и смогли её реализовать на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂