Najprostsze sortowania na maturę: bąbelkowe i przez wstawianie - zrozum to raz, a dobrze (Python i C++)

Na maturze z informatyki często nie chodzi o „najszybszy algorytm świata”, tylko o taki, który rozumiesz i potrafisz szybko napisać bez pomyłek. Dwa klasyki to sortowanie bąbelkowe (bubble sort) i sortowanie przez wstawianie (insertion sort). Są proste, stabilne (nie psują kolejności równych elementów) i świetne do nauki myślenia algorytmicznego.

Dlaczego w ogóle zaczynać od najprostszych sortowań?

• Uczysz się rozbijać problem na kroki i porównywać elementy parami.
• Widzisz, czym jest „pętelka w pętelce” (złożoność O(n²)) - to wraca w wielu zadaniach.
• Te wzorce (porównanie → zamiana → przesunięcie) później zobaczysz w bardziej zaawansowanych algorytmach.

1) Sortowanie bąbelkowe (bubble sort)

Intuicja: „Duże bąble wypływają na koniec”. W każdej rundzie przechodzisz po tablicy i zamieniasz sąsiadujące elementy, jeśli są w złej kolejności. Po pierwszym przejściu największy element ląduje na końcu, po drugim - drugi co do wielkości itd.

Przykład na żywo (krok po kroku)

Wejście: [5, 1, 4, 2] (rosnąco)

1. Runda 1: porównuj pary (5,1) → zamień → [1,5,4,2]; (5,4) → zamień → [1,4,5,2]; (5,2) → zamień → [1,4,2,5]. Największa „5” na końcu.
2. Runda 2: (1,4) ok, (4,2) → zamień → [1,2,4,5]. Teraz „4” na swoim miejscu.
3. Runda 3: (1,2) ok. Koniec - posortowane.

Ulepszenie: jeśli w danej rundzie nie było żadnej zamiany, to całość już jest posortowana - możesz przerwać wcześniej.

Kod - Python (z wczesnym zakończeniem)

def bubble_sort(a):
    n = len(a)
    for i in range(n-1):
        swapped = False
        for j in range(n-1-i):  # -i, bo ostatnie i elementów już "na miejscu"
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break
    return a

Kod - C++ (czytelna wersja szkolna)

#include <bits/stdc++.h>
using namespace std;

void bubble_sort(vector<int>& a){
    int n = (int)a.size();
    for(int i=0; i<n-1; i++){
        bool swapped = false;
        for(int j=0; j<n-1-i; j++){
            if(a[j] > a[j+1]){
                swap(a[j], a[j+1]);
                swapped = true;
            }
        }
        if(!swapped) break; // już posortowane
    }
}

Kiedy bubble sort ma sens?

• Gdy masz bardzo małe zbiory danych (kilkanaście liczb) i liczy się prostota.
• Gdy w zadaniu trzeba „symulować” właśnie takie zachowanie (zamiany sąsiadów, liczenie liczby zamian itp.).
• Gdy chcesz wykryć, że dane już prawie posortowane - wczesne zakończenie przyspiesza.

2) Sortowanie przez wstawianie (insertion sort)

Intuicja: układasz karty w ręku. Masz już posortowaną lewą część i „wkładasz” do niej następny element na właściwe miejsce, przesuwając większe w prawo.

Przykład na żywo (krok po kroku)

Wejście: [5, 1, 4, 2]

1. Weź 1 (drugi element). W posortowanej części [5] znajdź miejsce dla 1 → przesuń 5 w prawo → [5,5,4,2] → wstaw 1 na początek → [1,5,4,2].
2. Weź 4. W [1,5] znajdź miejsce → 5 przesuwa się w prawo → [1,5,5,2] → wstaw 4 → [1,4,5,2].
3. Weź 2. W [1,4,5] przesuwamy 5, potem 4 → [1,4,5,5] → [1,4,4,5] → wstaw 2 → [1,2,4,5].

Kod - Python (klasyczny, czytelny)

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key
    return a

Kod - C++ (wersja szkolna)

#include <bits/stdc++.h>
using namespace std;

void insertion_sort(vector<int>& a){
    for(int i=1; i<(int)a.size(); i++){
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > key){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

Kiedy insertion sort ma sens?

• Dane są małe lub „prawie posortowane” - insertion sort wtedy bywa bardzo szybki.
• Chcesz prostą, stabilną metodę do wstawiania elementów w odpowiednie miejsca.
• Potrzebujesz łatwej do wytłumaczenia logiki w zadaniu opisowym.

Bubble vs Insertion - którą metodę wybrać?

Typowe pułapki i jak ich uniknąć

• Błędne zakresy pętli: w bubble pamiętaj o `n-1-i`; w insertion - start od `i=1`.
• Porównywanie złych elementów: w bubble zawsze sprawdzasz `a[j]` z `a[j+1]`; w insertion porównujesz `a[j]` z `key`.
• Nadpisania w insertion: najpierw przesuwasz większe elementy w prawo, dopiero na końcu wstawiasz `key` pod `a[j+1]`.
• Sortowanie malejąco: odwróć znak porównania (`>` → `<`) - i już.

Mini-zadania

1. Policz liczbę zamian wykonanych przez bubble sort na tablicy wejściowej (wypisz liczbę).
2. Dla insertion sort wypisz indeksy, na które realnie trafił `key` w kolejnych krokach.
3. Dane są liczby, z których część się powtarza. Pokaż, że algorytm jest stabilny (równe elementy zachowują kolejność).
4. Zmodyfikuj oba algorytmy, by sortowały malejąco.

FAQ - najczęstsze pytania

• Czy na maturze muszę znać quicksort/merge sort? Warto kojarzyć, ale do wielu zadań wystarczą bubble/insertion. Liczy się poprawność i czytelność.
• Który z tych dwóch jest lepszy? Jeśli dane są „prawie posortowane” - insertion. Jeśli chcesz liczyć zamiany sąsiadów - bubble.
• Czy mogę użyć wbudowanego sortowania? Jeśli polecenie pozwala - tak (Python: `sorted`, C++: `sort`). Ale umiejętność napisania prostego sortowania bywa wymagana.

Podsumowanie - co zapamiętać?

• Bubble sort: zamieniaj sąsiadów, zakończ wcześniej jeśli brak zamian.
• Insertion sort: „wkładanie karty” - przesuwaj większe elementy, wstaw `key` na właściwe miejsce.
• Oba są stabilne i proste do napisania pod presją czasu.
• Dla małych/prawie posortowanych danych - insertion bywa bardzo praktyczny.