Python - bubble sort

Uczymy się pisać algorytm bubble sort w języku Python. Pierwszy artykuł z serii o algorytmach sortowania w Pythonie. Absolutny must-know!

Bubble sort – pętla zewnętrzna od lewej do końca

Zakładam, że mniej więcej znamy naturę problemu, jeżeli nie – możemy sprawdzić sobie jakąś wizualizację online. Zaczynamy z takim kodem:

lst = ['a', 'b', 'c', 'd', 'e']
def bubble_sort(arr):
    pass

Naszym celem jest napisanie pętli, która idzie od początku do ostatniego elementu. W następnej iteracji – od początku do przedostatniego i tak do końca.

lst = ['a', 'b', 'c', 'd', 'e']
def bubble_sort(arr):
    end = len(arr)
    while end > 0:
        print(arr[0:end])
        end -=1

Używamy pętli while, ponieważ do (nauki) algorytmów w Pythonie for Pythonowe się po prostu nie nadaje (możesz mi wierzyć na słowo, albo nie).

Nasz wynik:

['a', 'b', 'c', 'd', 'e']
['a', 'b', 'c', 'd']
['a', 'b', 'c']
['a', 'b']
['a']

Już teraz możemy zastosować małą optymalizację. Nasz algorytm operuje na bąbelkach, czyli dwu-elementowych parach i ta ostatnia, jednoelementowa lista jest niepotrzebna – wtedy już wszystko będzie posortowane:

lst = ['a', 'b', 'c', 'd', 'e']
def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        print(arr[0:end])
        end -= 1

bubble_sort(lst)
# ['a', 'b', 'c', 'd', 'e']
# ['a', 'b', 'c', 'd']
# ['a', 'b', 'c']
# ['a', 'b']

Bąble bubble sort – pętla wewnętrzna algorytmu

Widzimy, jak działa pętla zewnętrzna – idzie od lewej do prawej do samego końca. W każdej kolejnej iteracji robi to samo, ale koniec kurczy się od prawej o jeden element.

Wewnątrz tej pętli tworzymy drugą pętlę, która bąbelkuje od lewej do prawej do aktualnego końca pętli zewnętrznej. Bąbelek to 2 elementy, które w następnym kroku będą ze sobą porównywane.

Zróbmy sobie te bąbelki:

lst = ['a', 'b', 'c', 'd', 'e']
def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        left_bubble = 0
        right_bubble = 1
        while right_bubble < end:
            print((arr[left_bubble], arr[right_bubble]))
            left_bubble += 1
            right_bubble += 1
        end -= 1

bubble_sort(lst)

Chciałem być tak czytelny, jak to tylko możliwe. Sztuczka z podwójnym nawiasem wewnątrz print jest po to, aby ładnie nam się wynik wyświetlił w postaci tupli:

('a', 'b')
('b', 'c')
('c', 'd')
('d', 'e')
('a', 'b')
('b', 'c')
('c', 'd')
('a', 'b')
('b', 'c')
('a', 'b')

Logika sortowania – przesuwamy większe elementy na prawo

Możemy teraz zacząć implementować logikę, czyli wychodzimy poza te literki, które służyły nam do wizualizacji i idziemy w liczby:

nums = [1,1,3,10,5,8,7,4,1]

def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        left_bubble = 0
        right_bubble = 1
        while right_bubble < end:
            print((arr[left_bubble], arr[right_bubble]))
            left_bubble += 1
            right_bubble += 1
        end -= 1

bubble_sort(nums)

Musimy sprawdzić, czy lewy nie jest większy od prawego, i jeżeli tak – zamienić je:

nums = [1,1,3,10,5,8,7,4,1]

def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        left_bubble = 0
        right_bubble = 1
        while right_bubble < end:
            if arr[left_bubble] > arr[right_bubble]:
                arr[left_bubble], arr[right_bubble] = arr[right_bubble], arr[left_bubble]
            left_bubble += 1
            right_bubble += 1
        end -= 1

bubble_sort(nums)
print(nums)
#[1, 1, 1, 3, 4, 5, 7, 8, 10]

Optymalizacja bubble sort – była zamiana czy nie?

Zastanówmy się, co się stanie, gdy nasz algorytm, na początku bądź w którejś iteracji będzie przechodził po takiej liście:

nums = [1,2,3,4,5]

Pierwsza iteracja pętli głównej ustawia end na 5 (4 jeżeli idzie o indeks). Iteracje pętli wewnętrznej porównują 1 i 2, 2 i 3, 3 i 4, 4 i 5. Nie dokonują żadnej zmiany.

Skoro nie dokonują żadnej zmiany, to lista jest już posortowana. Pozostaje napisać mechanizm, który odpowiednio wykrywa, czy pętla wewnętrzna dokonała zmiany czy nie, wtedy wiemy, kiedy sortowanie należy zakończyć, bo nie ma już co sortować.

nums = [1,2,3,4,5]

def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        left_bubble = 0
        right_bubble = 1
        # TU NOCHANGE = TRUE
        while right_bubble < end:
            if arr[left_bubble] > arr[right_bubble]:
                arr[left_bubble], arr[right_bubble] = arr[right_bubble], arr[left_bubble]
                # JEŻELI BYŁA ZAMIANA, NOCHANGE TO FALSE
            left_bubble += 1
            right_bubble += 1
        # JEŻELI JESTEŚMY TUTAJ I NOCHANGE = TRUE, ZNACZY, ŻE NIE BYŁO ZAMIANY
        end -= 1

Piszemy:

nums = [1,2,3,5,4]

def bubble_sort(arr):
    end = len(arr)
    while end > 1:
        left_bubble = 0
        right_bubble = 1
        no_change = True
        while right_bubble < end:
            if arr[left_bubble] > arr[right_bubble]:
                arr[left_bubble], arr[right_bubble] = arr[right_bubble], arr[left_bubble]
                no_change = False
            left_bubble += 1
            right_bubble += 1
        if no_change:
            print("break!")
            break
        end -= 1

bubble_sort(nums)
print(nums)
# break!
# [1, 2, 3, 4, 5]

Jak widać przy prawie-posortowanej liście dokonaliśmy optymalizacji. Pętla główna wykonała się jeden raz (dwa razy). Bąbelkowa pętla wewnętrzna porównała każdy element z każdym i tylko 5 było większe niż 4.

Za drugim obrotem pętla bąbelkowa porównywała 1,2,3,4 ze sobą zaś pętla zewnętrzna stopowała przed 5, która była już posortowana. Pętla bąbelkowa nie wykonała ani jednej podmianki, więc można było sortowanie zakończyć przed czasem.

Python – bubble sort

Bubble sort – pętla zewnętrzna od lewej do końca

Bąble bubble sort – pętla wewnętrzna algorytmu

Logika sortowania – przesuwamy większe elementy na prawo

Optymalizacja bubble sort – była zamiana czy nie?