Алгоритм пузырьковой сортировки — реализация на Python | OTUS
🔥 Успейте получить скидку!
Только до 27.01 можно приобрести курсы со скидкой 25%. Торопитесь!
Выбрать курс

Курсы

Программирование
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Разработчик C#
-25%
Алгоритмы и структуры данных
-25%
Backend-разработчик на PHP
-25%
JavaScript Developer. Professional
-25%
Team Lead
-25%
Golang Developer. Professional
-25%
Agile Project Manager
-25%
Flutter Mobile Developer
-25%
Android Developer. Professional
-11%
MS SQL Server Developer
-8%
C++ Developer. Professional Framework Laravel Cloud Solution Architecture Highload Architect Reverse-Engineering. Professional Kotlin Backend Developer React.js Developer VOIP инженер Нереляционные базы данных Scala-разработчик Супер-практикум по использованию и настройке GIT IoT-разработчик JavaScript Developer. Basic Advanced Fullstack JavaScript developer Unity Game Developer. Professional Супер-интенсив Azure
Инфраструктура
Супер-интенсив "Версионирование и командная работа с помощью Git"
-30%
Administrator Linux. Professional
-25%
Супер-интенсив «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Administrator Linux. Advanced
-25%
Infrastructure as a code in Ansible
-25%
Network engineer
-25%
MS SQL Server Developer
-8%
Cloud Solution Architecture Highload Architect Разработчик голосовых ассистентов и чат-ботов Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Архитектор сетей Супер-интенсив «IaC Ansible»
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться
Только до 27 января!
🔥 СКИДКА 25% на курсы OTUS!