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:

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

  1. Wstęp do kursu
  2. FizzBuzz
  3. Najmniejsza i największa liczba
  4. Zliczanie liter
  5. Sortowanie bąbelkowe <– bieżąca lekcja
  6. Suma dwóch liczb
  7. Wyszukiwanie binarne
  8. Gra w orła i reszkę
  9. Podsumowanie oraz dalsze kroki

def sortowanie_babelkowe(lista):