Алгоритм пузырьковой сортировки — реализация на Python | OTUS
⚡ Открываем подписку на курсы!
Проходите параллельно 3 онлайн-курса в месяц по цене одного.
Подробнее

Курсы

Программирование
Flutter Mobile Developer Подготовка к сертификации Oracle Java Programmer (OCAJP)
-8%
Супер-интенсив «СУБД в высоконагруженных системах»
-18%
Алгоритмы и структуры данных
-12%
Web-разработчик на Python
-11%
Архитектура и шаблоны проектирования
-14%
Team Lead
-15%
iOS-разработчик. Базовый курс
-23%
Разработчик на Spring Framework Python Developer. Basic
-16%
C# ASP.NET Core разработчик
-18%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Android-разработчик. Базовый курс
-10%
C++ Developer. Professional Разработчик C# AWS для разработчиков Software Architect Unity Game Developer. Basic Разработчик голосовых ассистентов и чат-ботов Backend-разработка на Kotlin React.js Developer Разработчик Node.js Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Advanced Fullstack JavaScript developer
Инфраструктура
Супер-интенсив «СУБД в высоконагруженных системах»
-18%
PostgreSQL
-10%
IoT-разработчик
-12%
Administrator Linux. Professional
-11%
Базы данных
-19%
Administrator Linux.Basic
-18%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-6%
Сетевой инженер AWS для разработчиков Software Architect Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться