Сортировка пузырьком: пример и объяснение

Алгоритм сортировки пузырьком — самый простой, но и самый медленный алгоритм сортировки. Рассмотрим пример сортировки пяти элементов.

Пример сортировки

Алгоритм сортировки пузырьком состоит из раундов.

Раунд 1: Сравниваем пары элементов. Если первый элемент больше второго, меняем их местами.

• 8 > 7, меняем: 7, 8, 5, 6, 1
• 8 > 5, меняем: 7, 5, 8, 6, 1
• 8 > 6, меняем: 7, 5, 6, 8, 1
• 8 > 1, меняем: 7, 5, 6, 1, 8

После первого раунда один элемент (8) находится на своём месте.

Раунд 2:

• 7 > 5, меняем: 5, 7, 6, 1, 8
• 7 > 6, меняем: 5, 6, 7, 1, 8
• 7 > 1, меняем: 5, 6, 1, 7, 8

Теперь два элемента (8 и 7) на своих местах.

Раунд 3:

• 5 > 6, (нет обмена)
• 6 > 1, меняем: 5, 1, 6, 7, 8

Три элемента (8, 7, 6) на своих местах.

Раунд 4:

• 5 > 1, меняем: 1, 5, 6, 7, 8

Все элементы отсортированы по возрастанию.

Вычислительная сложность

Для пяти элементов потребовалось четыре раунда. Количество сравнений: 4 + 3 + 2 + 1 = 10.

Для n элементов будет n-1 раундов. Общая формула для количества сравнений: n(n-1)/2.

Для 100 элементов количество сравнений приблизительно 5000, что очень много. Временная сложность алгоритма — O(n²), что очень медленно. Пространственная сложность — O(1), так как не требуются дополнительные переменные; обмен элементов происходит «на месте».

Реализация на Python

def bubble_sort(l):
    n = len(l)
    for i in range(n):
        for j in range(0, n-i-1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
    return l

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

Оптимизированная реализация на Python

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

Реализация на JavaScript

(Код реализации на JavaScript не предоставлен в исходном тексте и не может быть добавлен без ухудшения качества ответа)

Алгоритм сортировки пузырьком, несмотря на простоту, имеет квадратичную временную сложность, что делает его неэффективным для больших массивов данных. Однако его оптимизированные версии могут показать лучшие результаты для уже отсортированных или частично отсортированных массивов.