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.

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)

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ż.

Przykładowe zadanie maturalne z sortowania z rozwiązaniem krok po kroku

Poniżej znajdziesz typowe zadanie maturalne dotyczące sortowania wraz z pełnym rozwiązaniem.

Zadanie: Policz liczbę zamian w sortowaniu bąbelkowym

Treść zadania: Napisz program, który dla tablicy liczb [5, 1, 4, 2, 8] wykona sortowanie bąbelkowe i wypisze, ile zamian (swap) zostało wykonanych do momentu posortowania tablicy.

Analiza krok po kroku na papierze

Prześledźmy sortowanie tablicy [5, 1, 4, 2, 8]:

Tablica początkowa: [5, 1, 4, 2, 8]

Runda 1:
  (5,1) → zamiana → [1, 5, 4, 2, 8]  ✓ zamiana #1
  (5,4) → zamiana → [1, 4, 5, 2, 8]  ✓ zamiana #2
  (5,2) → zamiana → [1, 4, 2, 5, 8]  ✓ zamiana #3
  (5,8) → ok
  Stan: [1, 4, 2, 5, 8]

Runda 2:
  (1,4) → ok
  (4,2) → zamiana → [1, 2, 4, 5, 8]  ✓ zamiana #4
  (4,5) → ok
  Stan: [1, 2, 4, 5, 8]

Runda 3:
  (1,2) → ok, (2,4) → ok, (4,5) → ok
  Brak zamian – KONIEC

Odpowiedź: 4 zamiany

Rozwiązanie w Pythonie

def bubble_sort_count(arr):
    n = len(arr)
    licznik_zamian = 0
    
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                licznik_zamian += 1
                swapped = True
        if not swapped:
            break
    
    return licznik_zamian

# Test
tablica = [5, 1, 4, 2, 8]
zamiany = bubble_sort_count(tablica)
print(f'Posortowana tablica: {tablica}')
print(f'Liczba zamian: {zamiany}')  # 4

Wskazówka na maturę

Liczba zamian w sortowaniu bąbelkowym jest równa liczbie inwersji w tablicy. Inwersja to para elementów (i, j), gdzie i < j, ale arr[i] > arr[j]. To częste pytanie na maturze!

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.

Szukasz więcej praktyki? Sprawdź pełny kurs do matury z informatyki.