Алгоритм пузырьковой сортировки — реализация на Python | OTUS
💥 Пока ты ждешь — другие качаются!
Мы создали лучшие условия, чтобы ты начал учиться прямо сейчас. Пиши в чат и получи скидку ➞
Написать в чат

Курсы

Программирование
Web-разработчик на Python
-20%
Разработчик Python
-20%
Разработчик на Spring Framework Разработчик Golang
-20%
iOS Разработчик. Продвинутый курс v 2.0.
-20%
C# ASP.NET Core разработчик
-20%
Vue.js разработчик Архитектор программного обеспечения Разработчик C++ MS SQL Server разработчик Android-разработчик. Базовый курс Архитектор высоких нагрузок Backend-разработчик на PHP Алгоритмы для разработчиков Программист 1С VOIP инженер Разработчик Java Enterprise AWS для разработчиков PostgreSQL Cloud Solution Architecture CI/CD Интенсив «Оптимизация в Java»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

Algo_Deep_3.4-5020-66ad16.png

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

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

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

Следовательно, алгоритм надо оптимизировать, для чего необходимо понимать, когда его останавливать, то есть знать, когда список отсортирован. Для остановки алгоритма следует ввести переменную-флаг. Если значения меняются местами, мы устанавливаем флаг в значение 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(n2), где n — число элементов списка.

Вот и всё!

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

Источник

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🎁 Дарим сертификаты на скидку!
Запишитесь на июньскую трансляцию интересного вам дня открытых дверей и получите скидочный сертификат ➞