Sortowanie Bąbelkowe (Bubble Sort) na Maturze z Informatyki

def bubble_sort(tab):
    n = len(tab)
    
    # Pętla zewnętrzna (przejścia)
    for i in range(n - 1):
        # Pętla wewnętrzna (porównania)
        # Optymalizacja: n-i-1, bo po i-tym przejściu
        # i-elementów na końcu jest już posortowanych
        for j in range(0, n - i - 1):
            # Porównanie sąsiadów
            if tab[j] > tab[j + 1]:
                # Zamiana miejscami
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
    return tab

dane = [64, 34, 25, 12, 22, 11, 90]
print(f"Przed: {dane}")
bubble_sort(dane)
print(f"Po: {dane}")

To jest klasyczna, zoptymalizowana implementacja. `n = len(tab)`. Pętla zewnętrzna `i` idzie od 0 do `n-2`. Pętla wewnętrzna `j` idzie od 0 do `n-i-2`. W Pythonie zamiana `tab[j], tab[j+1] = tab[j+1], tab[j]` jest bardzo wygodna.

def bubble_sort_opt(tab):
    n = len(tab)
    for i in range(n - 1):
        swapped = False # Flaga sprawdzająca zamiany
        for j in range(0, n - i - 1):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                swapped = True
        
        # Jeśli w całym przejściu nie było ani jednej zamiany,
        # to tablica jest już posortowana. Możemy przerwać.
        if not swapped:
            break
    return tab

dane = [1, 2, 3, 5, 4, 6]
print(bubble_sort_opt(dane))

To jest ulepszona wersja. Dodajemy flagę `swapped`. Jeśli wewnętrzna pętla przejdzie całą tablicę i nie dokona *ani jednej* zamiany, oznacza to, że tablica jest już posortowana. Wtedy `break` przerywa pętlę zewnętrzną. To znacznie przyspiesza algorytm dla danych częściowo posortowanych.

#include <iostream>
#include <vector>
#include <algorithm> // dla std::swap

using namespace std;

void bubble_sort(vector<int>& tab) {
    int n = tab.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j + 1]) {
                // Używamy std::swap do zamiany
                swap(tab[j], tab[j + 1]);
            }
        }
    }
}

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

Logika jest identyczna jak w Pythonie. Używamy `vector` jako naszej tablicy. Do zamiany elementów najwygodniej użyć funkcji `swap(a, b)` z biblioteki `<algorithm>`. Zamiast `vector` można też użyć statycznej tablicy `int dane[]`, ale `vector` jest bardziej elastyczny.