Sortowanie Bąbelkowe (Bubble Sort)

Wyobraź sobie, że masz na półce ciąg książek o różnej grubości i chcesz je ułożyć od najcieńszej do najgrubszej. Sortowanie bąbelkowe to najprostszy (choć nie najszybszy) sposób, żeby to zrobić.

Zasada jest banalna: porównujesz dwie sąsiednie książki. Jeśli ta po lewej jest grubsza od tej po prawej – zamieniasz je miejscami. I tak idziesz od początku do końca półki. Gdy dojdziesz do końca, największa (najgrubsza) książka na pewno "wypłynie" na sam koniec, zupełnie jak bąbelek powietrza w wodzie.

Potem zaczynasz od nowa, ignorując już ułożony koniec.

Implementacja

Zgodnie z wymogami maturalnymi, poniżej znajdziesz implementację w C++ oraz Pythonie.

C++

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    // Zewnętrzna pętla: ile razy musimy przejść przez tablicę
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        // Wewnętrzna pętla: porównuje sąsiednie elementy
        // n - i - 1, bo 'i' ostatnich elementów jest już na swoim miejscu
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // Wbudowana funkcja zamiany
                swapped = true;
            }
        }
        
        // Optymalizacja: jeśli w całym przejściu nie było zamian, tablica jest posortowana
        if (!swapped) break;
    }
}

int main() {
    vector<int> liczby = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(liczby);
    
    for(int x : liczby) cout << x << " ";
    return 0;
}

Python

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # W Pythonie zamiana (swap) jest bardzo prosta
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                
        # Jeśli nic nie zamieniono, kończymy
        if not swapped:
            break

liczby = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(liczby)
print(liczby)

🧠 Dla Dociekliwych

Dlaczego uczymy się optymalizacji ze zmienną swapped? Bez flagi swapped, algorytm zawsze wykona pełne $n \times n$ iteracji, nawet jeśli tablica od początku była idealnie posortowana! Z flagą swapped, dla posortowanej tablicy algorytm zatrzyma się po pierwszym przejściu, co daje nam złożoność optymistyczną $O(n)$.

Dlaczego na maturze zazwyczaj go unikamy? Jego złożoność czasowa w najgorszym przypadku to $O(n^2)$. Oznacza to, że dla 10 000 elementów komputer musi wykonać około 100 milionów operacji! Jeśli w zadaniu maturalnym masz do posortowania milion liczb z pliku, sortowanie bąbelkowe po prostu przekroczy limit czasu (tzw. TLE - Time Limit Exceeded). Do takich zadań lepiej użyć wbudowanego sort() (C++) lub .sort() (Python), które korzystają z szybszych algorytmów np. Quicksort lub Timsort ($O(n \log n)$).