Bubble Sort in Python

1 min


Вступление

Для большинства людей Bubble Sort, вероятно, является первым алгоритмом сортировки, о котором они слышали в своем курсе информатики.

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

Пузырьковая сортировка

Идея Bubble Sort очень проста: мы смотрим на пары соседних элементов в массиве, по одной паре за раз, и меняем их позиции, если первый элемент больше второго, или просто перемещаемся, если это не так. Давайте посмотрим на пример и отсортировать массив 8, 5, 3, 1, 4, 7, 9:

пузырьковая сортировка

Если вы сосредоточитесь на первом номере, номер 8Вы можете видеть, как он «пузырится» массив в правильном месте. Затем этот процесс повторяется для числа 5 и так далее.

Реализация

С визуализацией в стороне, давайте продолжим и реализуем алгоритм. Опять же, это очень просто:

def bubble_sort(our_list):
    # We go through the list as many times as there are elements
    for i in range(len(our_list)):
        # We want the last pair of adjacent elements to be (n-2, n-1)
        for j in range(len(our_list) - 1):
            if our_list[j] > our_list[j+1]:
                # Swap
                our_list[j], our_list[j+1] = our_list[j+1], our_list[j]

Теперь давайте заполним список и назовем алгоритм для него:

our_list = [19, 13, 6, 2, 18, 8]
bubble_sort(our_list)
print(our_list)

Выход:

[2, 6, 8, 13, 18, 19]

оптимизация

Простая реализация сделала свое дело, но здесь мы можем сделать две оптимизации.

Когда никакие перестановки не сделаны, это означает, что список отсортирован. Хотя, с ранее реализованным алгоритмом, он будет продолжать оценивать остальную часть списка, даже если это действительно не нужно. Чтобы исправить это, мы будем держать boolean пометьте и проверьте, были ли какие-либо перестановки в предыдущей итерации.

Если перестановки не выполняются, алгоритм должен остановиться:

def bubble_sort(our_list):
    # We want to stop passing through the list
    # as soon as we pass through without swapping any elements
    has_swapped = True

    while(has_swapped):
        has_swapped = False
        for i in range(len(our_list) - 1):
            if our_list[i] > our_list[i+1]:
                # Swap
                our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
                has_swapped = True

Другая оптимизация, которую мы можем сделать, использует тот факт, что Bubble Sort работает таким образом, что самые большие элементы в определенной итерации заканчиваются в конце массива.

Первый раз, когда мы проходим через список позиции N гарантированно будет самый большой элемент, второй раз мы проходим через позицию н-1 гарантированно будет вторым по величине элементом и так далее.

Это означает, что с каждой последовательной итерацией мы можем смотреть на один элемент меньше, чем раньше. Точнее, в К-я итерация, нужно только посмотреть на первую n – k + 1 элементы:

def bubble_sort(our_list):
    has_swapped = True

    num_of_iterations = 0

    while(has_swapped):
        has_swapped = False
        for i in range(len(our_list) - num_of_iterations - 1):
            if our_list[i] > our_list[i+1]:
                # Swap
                our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
                has_swapped = True
        num_of_iterations += 1

Сравнение времени

Давайте продолжим и сравним время, необходимое для каждого из этих фрагментов кода, чтобы отсортировать один и тот же список тысячу раз, используя timeit модуль:

Unoptimized Bubble Sort took: 0.0106407
Bubble Sort with a boolean flag took: 0.0078251
Bubble Sort with a boolean flag and shortened list took: 0.0075207

Между последними двумя подходами нет большой разницы из-за того, что список очень короткий, но для больших списков – вторая оптимизация может иметь огромное значение.

Вывод

В самом неэффективном подходе Bubble Sort проходит н-1 итерации, глядя на н-1 пары соседних элементов. Это дает ему временную сложность На2)как в лучшем, так и в среднем случае. На2) считается довольно ужасным для алгоритма сортировки.

У него есть O (1) сложность пространства, но этого недостаточно, чтобы компенсировать его недостатки в других областях.

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


0 Comments

Ваш адрес email не будет опубликован. Обязательные поля помечены *