Sortowanie bąbelkowe w Python

Ciężko rozmawiać o podstawach informatyki, nie wspominając algorytmie sortowania bąbelkowego. I o nim również często rozmawia się na rozmowach kwalifikacyjnych.

Problem: mamy podaną listę liczb. Np. A = [2,1,5,3,6]. Należy posortować ją rosnąco, za pomocą algorytmu bąbelkowego.

Sortowanie bąbelkowe: jest to prosta i najbardziej znana metoda sortowania. Polega ona na:

’przejściu’ przez poszczególne elementy list, np za pomocą pętli 'for’,
sprawdzeniu czy element następny na liście, jest mniejszy. Jeżeli tak, zastąpieniu ich miejscami.
Powtarzamy czynność, dla kolejnego elementu i sprawdzamy czy kolejny jest mniejszy. Jeżeli tak, to zamieniamy miejscami, itd
W momencie, kiedy dojdziemy do końca listy, na jej końcu powinna znajdować się największa liczba z listy,
Następnie powtarzamy naszą pętlę 'for’, zaczynając od początku.
kończymy wtedy, gdy wykonamy interakcję bez zmiany kolejności żadnego elementu

Przykład:

Iteracja 1: [2,0,5,1,6,3] (0<2) – > [0,2,5,1,6,3](5>2) → [0,2,5,1,6,3](1<5) → [0,2,1,5,6,3] (6>5)→[0,2,1,5,6,3](3<6) -> [0,2,1,5,3,6]

Iteracja 2: [0,2,1,5,3,6] (1<2) → [0,1,2,5,3,6] (5>2) → [0,1,2,5,3,6] (3<5) → [0,1,2,3,5,6] (6>5) → [0,1,2,3,5,6]

Iteracja 3: [0,1,2,3,5,6] /// algorytm wykonuje finalną iterację, po czym kończy działanie

Praktyczna porada:

Czasami takie zadania, są bardzo trudne do rozwiązania 'w głowie’, natomiast stają się proste, jak tylko weźmiemy kartkę i długopis, po czym sobie cały ten proces z wizualizujemy. Samodzielnie:)

Rozwiązanie:

Przykładowy kod:

https://www.youtube.com/watch?v=9JZh82mGB1M

def sortowanie_babelkowe(lista):

    n = len(lista)
    
    while n > 1:

        zamien = False
        for l in range(0, n-1):

            if lista[l] > lista[l+1]:
                lista[l], lista[l+1] = lista[l+1], lista[l]
                zamien = True
                
        n -= 1
        print(lista)
        if zamien == False: break
        
    return lista
        
sortowanie_babelkowe([5,6,-1,0])

Ćwiczenia Python, dla początkujących