Algorytmy sortowania - które warto znać na maturę?

Umiejętność sortowania danych to jedna z fundamentalnych kompetencji w informatyce, a zadania z tego zakresu regularnie pojawiają się na maturze. Choć istnieje wiele algorytmów sortowania, na potrzeby egzaminu wystarczy solidne zrozumienie kilku kluczowych metod. W tym artykule przeprowadzimy Cię przez algorytmy, które każdy maturzysta powinien znać, wyjaśniając ich logikę, analizując wydajność i pokazując praktyczne implementacje.

Dlaczego złożoność obliczeniowa jest tak ważna?

Zanim przejdziemy do konkretnych algorytmów, musimy zrozumieć pojęcie złożoności obliczeniowej. Określa ona, jak bardzo wzrasta czas działania algorytmu (złożoność czasowa) lub zapotrzebowanie na pamięć (złożoność pamięciowa) wraz ze wzrostem liczby danych. Na maturze najczęściej spotkasz się z notacją „Wielkiego O”, np. O(n^2) oznacza złożoność kwadratową, a O(n \log n) logarytmiczno-liniową. Zrozumienie tej różnicy jest kluczowe - algorytm o złożoności O(n^2) dla miliona elementów będzie działał drastycznie wolniej niż algorytm O(n \log n).

Podstawowe algorytmy sortowania - absolutna konieczność

Te trzy algorytmy są najprostsze do zrozumienia i zaimplementowania. Mimo że są nieefektywne dla dużych zbiorów danych (wszystkie mają złożoność O(n^2)), ich znajomość jest wymagana na maturze, ponieważ doskonale ilustrują podstawowe koncepcje algorytmiczne.

1. Sortowanie Bąbelkowe (Bubble Sort)

To najprostszy z algorytmów. Działa poprzez wielokrotne przechodzenie przez listę, porównywanie sąsiednich elementów i zamienianie ich miejscami, jeśli są w złej kolejności. Proces powtarza się do momentu, gdy podczas jednego przejścia nie zostanie wykonana żadna zamiana. Nazwa pochodzi od sposobu, w jaki największe elementy „wypływają” na koniec tablicy jak bąbelki.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # Ostatnie i elementów jest już na swoim miejscu
        for j in range(0, n - i - 1):
            # Porównaj sąsiednie elementy
            if arr[j] > arr[j + 1]:
                # Zamień je miejscami
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Przykład
liczby = [64, 34, 25, 12, 22, 11, 90]
print(f"Sortowanie bąbelkowe: {bubble_sort(liczby)}")

2. Sortowanie przez Wstawianie (Insertion Sort)

Algorytm ten buduje posortowaną listę krok po kroku. Dzieli tablicę na dwie części: posortowaną (na początku zawiera tylko pierwszy element) i nieposortowaną. Następnie pobiera kolejne elementy z części nieposortowanej i wstawia je w odpowiednie miejsce w części posortowanej. Jest intuicyjny i przypomina układanie kart w ręku.

def insertion_sort(arr):
    # Przechodzimy od drugiego elementu
    for i in range(1, len(arr)):
        klucz = arr[i] # Aktualnie wstawiany element
        j = i - 1
        # Przesuwamy elementy większe od klucza w prawo
        while j >= 0 and klucz < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # Wstawiamy klucz w odpowiednie miejsce
        arr[j + 1] = klucz
    return arr

# Przykład
liczby = [12, 11, 13, 5, 6]
print(f"Sortowanie przez wstawianie: {insertion_sort(liczby)}")

3. Sortowanie przez Wybieranie (Selection Sort)

Jego logika również jest prosta. Algorytm dzieli tablicę na część posortowaną i nieposortowaną. W każdej iteracji wyszukuje najmniejszy element w nieposortowanej części i zamienia go z pierwszym elementem tej części. W ten sposób posortowana część rozrasta się o jeden element w każdym kroku. Mimo złożoności O(n^2) ma tę zaletę, że wykonuje minimalną liczbę zamian.

Wydajniejsze algorytmy - warto znać zasadę działania

Chociaż implementacja tych algorytmów od zera jest rzadkością na maturze, musisz znać zasadę ich działania i złożoność. Opierają się one na strategii „Dziel i Zwyciężaj” (Divide and Conquer) i mają średnią złożoność czasową O(n \log n).

Sortowanie Szybkie (Quicksort)

To jeden z najpopularniejszych i najszybszych algorytmów. Jego działanie polega na wybraniu jednego elementu z tablicy (tzw. piwot lub element osiowy), a następnie podzieleniu pozostałych elementów na dwie grupy: mniejsze od piwota i większe od piwota. Następnie proces ten jest powtarzany rekurencyjnie dla obu podtablic. Jego słabością jest pesymistyczna złożoność O(n^2), która występuje przy niekorzystnym wyborze piwota (np. w już posortowanej tablicy).

Sortowanie przez Scalanie (Merge Sort)

Ten algorytm również stosuje metodę „Dziel i Zwyciężaj”. Dzieli tablicę na pół tak długo, aż pozostaną jednoelementowe zbiory. Następnie łączy (scala) te zbiory w pary, od razu je sortując. Proces jest powtarzany, aż do uzyskania jednej, posortowanej tablicy. Jego główną zaletą jest stabilność i gwarantowana złożoność czasowa O(n \log n) w każdym przypadku (najlepszym, średnim i pesymistycznym). Wadą jest większe zapotrzebowanie na pamięć (O(n) dodatkowej pamięci).

Podsumowanie i rekomendacje maturalne

Na maturę musisz perfekcyjnie opanować implementację sortowania bąbelkowego i przez wstawianie. Są one najczęstszym tematem zadań wymagających napisania kodu. Co do Quicksort i Merge Sort, kluczowe jest zrozumienie ich zasady działania, różnic między nimi oraz ich złożoności obliczeniowej. Poniższa tabela zbiera najważniejsze informacje:

Pamiętaj, że algorytmy to nie tylko sortowanie. Równie ważne są zagadnienia takie jak algorytm Euklidesa (NWD), sito Eratostenesa do znajdowania liczb pierwszych czy podstawy rekurencji. Solidne przygotowanie z tych wszystkich działów da Ci pewność siebie na egzaminie.