Алгоритм пузырьковой сортировки — реализация на Python

Алгоритм пузырьковой сортировки является довольно простым. Он выполняет итерации по списку и сравнивает элементы попарно, заодно меняя их местами. Это происходит до тех пор, пока крупные элементы не «всплывут» (аналогия с пузырьками воздуха) в начало списка. Более мелкие, соответственно, останутся на «дне».

Итак, поначалу происходит сравнение первых двух элементов списка. В случае, если первый элемент больше, элементы меняются местами. Если же элементы находятся в нужном порядке, всё остаётся без изменений. Второй этап — переход к следующей паре, значения которой сравниваются и меняются местами в случае необходимости. Так происходит, пока пары элементов в списке не закончатся.

Когда конец списка достигнут, процесс повторяется для каждого элемента. Но это неэффективно, если нам надо сделать в массиве, к примеру, лишь один обмен. Дело в том, что алгоритм будет повторяться n² раз, даже когда список уже отсортирован.

Следовательно, алгоритм надо оптимизировать, для чего необходимо понимать, когда его останавливать, то есть знать, когда список отсортирован. Для остановки алгоритма следует ввести переменную-флаг. Если значения меняются местами, мы устанавливаем флаг в значение True, дабы повторить процесс сортировки. В случае, когда перестановок не произошло, флаг остаётся False, в результате чего алгоритм останавливается. Давайте посмотрим, как это реализовать на практике.

Реализация

def bubble_sort(nums):  
    # Установим swapped в True, чтобы цикл запустился хотя бы раз
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                # Меняем элементы
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                # Установим swapped в True для последующей итерации
                swapped = True

# Проверим, что всё работает
random_list_of_nums = [5, 2, 1, 8, 4]  
bubble_sort(random_list_of_nums)  
print(random_list_of_nums)

Таким образом, алгоритм будет работать в цикле while и прерываться, если элементы ни разу не менялись местами. Сначала мы присвоим swapped значение True, чтобы наш алгоритм запустился хотя бы раз.

Что касается времени сортировки, то даже в самом худшем случае, если список изначально будет отсортирован по убыванию, затраты времени будут равны O(n²), где n — число элементов списка.

Вот и всё!

Возможно, вам также будет интересно: 1. «Оцениваем сложность алгоритмов: что такое О(log n)?» 2. «Реализуем пирамидальную сортировку на Python».

Источник