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

Об алгоритме:

В процессе пузырьковой сортировки соседние элементы массива сравниваются попарно, начиная с нуля. После первой итерации на месте последнего окажется наибольшее число, и это значение не будет использоваться в последующих итерациях (фактически мы получим n-1 сравнений). Затем алгоритм находит второй по величине элемент, который ставится на предпоследнее место, затем третий и т. д. В результате вместо нулевого элемента (не забываем, что нумерация в массиве начинается с нуля) будет наименьшее число, а на месте последнего элемента - наибольшее. Это означает, что можно сказать, что элементы от большего к меньшему «плавают» по аналогии с пузырьками.

Если вкратце:

• Текущий элемент сравнивается со следующим элементом.
• Если следующий меньше или больше, они меняются местами.
• Когда сортировка заканчивается, алгоритм останавливается, иначе возвращается к шагу №1.

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

Рассмотрим ручной пример:

Допустим у нас есть следующий массив:

7 2 9 4 1 0

В процессе первой итерации возьмем нулевой элемент (это 7) и сравним его с соседним. Поскольку семь больше двух, числа меняются местами. Это означает, что массив изменяется:

2 7 9 4 1 0

Далее происходит сравнение второго и третьего чисел. Поскольку изначально 9 больше семи, семерка остается на месте. Далее 9 последовательно сравнивается с остальными значениями и таким образом постепенно перемещается в самый конец массива (поскольку в массиве нет числа больше 9, девятка занимает свое заслуженное последнее место).

2 7 4 1 0 9

Первая итерация сделана, количество шагов уменьшилось на 1 (n-1), то есть 9 там, где должно быть. Этот номер больше не интересует.

На второй итерации все начинается с нулевого элемента массива (в нашем случае это двойка) с последующими сравнениями и смещениями. В результате массив будет выглядеть так:

2 4 1 0 7 9

И так далее. Итоговый вид массива после сортировки по методу пузырьком вы можете видеть ниже:

0 1 2 4 7 9

Реализация кода на Python:

def bubble_sort(array):
    # Определение длины массива
    length = len(array)
    # Внешний цикл, кол-во проходов
    for i in range(length):
        # Внутренний цикл, N-i-1 проходов
        for j in range(0, length-i-1):
            # Меняем элементы местами
            if array[j] > array[j+1]:
                temp = array[j]
                array[j] = array[j+1]
                array[j+1] = temp
                # Выводим информацию
                print(array)


# Задаем список из чисел
list_bubble = [7, 2, 9, 4, 1, 0]

# Передаем в функцию наш список
bubble_sort(list_bubble)

Результат:

>>> [2, 7, 9, 4, 1, 0]
>>> [2, 7, 4, 9, 1, 0]
>>> [2, 7, 4, 1, 9, 0]
>>> [2, 7, 4, 1, 0, 9]
>>> [2, 4, 7, 1, 0, 9]
>>> [2, 4, 1, 7, 0, 9]
>>> [2, 4, 1, 0, 7, 9]
>>> [2, 1, 4, 0, 7, 9]
>>> [2, 1, 0, 4, 7, 9]
>>> [1, 2, 0, 4, 7, 9]
>>> [1, 0, 2, 4, 7, 9]
>>> [0, 1, 2, 4, 7, 9]

Как видите, результат получился точно таким же, но за короткое время, чем бы мы делали это вручную.