Сортировка пузырьком.
Описание алгоритма и его реализация на Python

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

В процессе выполнения данного алгоритма элементы с большими значениями оказываются в конце списка, а элементы с меньшими значениями постепенно перемещаются по направлению к началу списка. Образно говоря, тяжелые элементы падают на дно, а легкие медленно всплывают подобно пузырькам воздуха. При этом в начале сортировки отсортированным становится конец списка, а не его начало.

В сортировке методом пузырька количество итераций внешнего цикла определяется длинной списка минус единица, так как когда второй элемент становится на свое место, то первый уже однозначно минимальный и не требует сортировки.

Количество итераций внутреннего цикла зависит от номера итерации внешнего цикла, так как конец списка уже отсортирован, и выполнять проход по этим элементам смысла нет.

Пусть имеется список из пяти элементов [6, 12, 4, 3, 8].

За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:

Результат: [6, 4, 3, 8, 12]

За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:

Результат: [4, 3, 6, 8, 12]

На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:

Результат: [3, 4, 6, 8, 12]

На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:

Результат: [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-1-i):
        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]

Для сортировки по убыванию достаточно изменить знак операции сравнения при if на обратный.

Примечание. Выражение a[j], a[j+1] = a[j+1], a[j] - это позволительная в Python сокращенная запись обмена значений двух переменных (в данном случае "ячеек" списка). Рабочий вариант для большинства языков программирования будет выглядеть так:

buff = a[j]
a[j] = a[j+1]
a[j+1] = buff

С помощью циклов while:

from random import randint

N = 10
# Вариант заполнения списка с помощью спискового выражения:
a = [randint(1, 99) for n in range(N)]
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):
    iterations = len(array) - 1
    for i in range(iterations):
        for j in range(iterations-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]


a = [randint(1, 99) for n in range(10)]
print(a)
bubble(a)
print(a)

Больше задач в PDF


Решение задач на Python

Все разделы сайта