Algorytmy sortowania danych – przegląd i porównanie wydajności
Sortowanie jest jednym z podstawowych problemów w informatyce. Polega na uporządkowaniu elementów zbioru według określonego kryterium (np. rosnąco lub malejąco). Wybór odpowiedniego algorytmu sortowania ma duże znaczenie, zwłaszcza w przypadku pracy z dużymi zbiorami danych. W artykule przedstawiono najważniejsze algorytmy sortowania, ich działanie oraz porównanie złożoności obliczeniowej.
1. Algorytmy proste
1.1 Sortowanie bąbelkowe (Bubble Sort)
- Idea: porównywanie sąsiednich elementów i zamiana ich miejscami, aż do uzyskania uporządkowanej listy.
- Złożoność:
- Czasowa:
- najlepszy przypadek: O(n) (dla już posortowanej tablicy),
- średni i najgorszy przypadek: O(n²).
- Pamięciowa: O(1).
- Czasowa:
- Zalety: prostota implementacji.
- Wady: bardzo niska wydajność przy większych zbiorach danych.
1.2 Sortowanie przez wstawianie (Insertion Sort)
- Idea: elementy są wstawiane kolejno na odpowiednie miejsce w już częściowo posortowanej tablicy.
- Złożoność:
- najlepszy przypadek: O(n),
- średni i najgorszy przypadek: O(n²).
- Zalety: dobre działanie dla małych lub częściowo posortowanych zbiorów.
- Wady: nieefektywne dla dużych zbiorów.
1.3 Sortowanie przez wybieranie (Selection Sort)
- Idea: w każdej iteracji wybierany jest najmniejszy element i przenoszony na początek.
- Złożoność:
- zawsze: O(n²).
- Zalety: prostota implementacji, niewielka liczba zamian elementów.
- Wady: duża liczba porównań, mała wydajność.
2. Algorytmy zaawansowane
2.1 Sortowanie szybkie (Quick Sort)
- Idea: wybór elementu (pivot), podział tablicy na dwie części i rekurencyjne sortowanie podtablic.
- Złożoność:
- najlepszy i średni przypadek: O(n log n),
- najgorszy przypadek: O(n²) (dla źle dobranego pivota).
- Pamięciowa: O(log n) (rekurencja).
- Zalety: bardzo szybki w praktyce.
- Wady: wrażliwy na wybór pivota.
2.2 Sortowanie przez scalanie (Merge Sort)
- Idea: dziel i zwyciężaj – dzielenie tablicy na mniejsze części i scalanie posortowanych fragmentów.
- Złożoność:
- zawsze: O(n log n).
- Pamięciowa: O(n) (potrzebne dodatkowe tablice).
- Zalety: stabilność, przewidywalny czas działania.
- Wady: wymaga dodatkowej pamięci.
2.3 Sortowanie przez kopcowanie (Heap Sort)
- Idea: budowa kopca i wyciąganie największego elementu, aż do uzyskania posortowanej listy.
- Złożoność:
- zawsze: O(n log n).
- Pamięciowa: O(1).
- Zalety: przewidywalność, brak dodatkowej pamięci.
- Wady: wolniejszy od Quick Sorta w praktyce.
3. Algorytmy specjalne
3.1 Sortowanie kubełkowe (Bucket Sort)
- Idea: rozdzielanie elementów do kubełków (przedziałów), a następnie sortowanie w każdym kubełku i scalanie wyników.
- Złożoność: O(n + k), gdzie k to liczba kubełków.
- Wady: zależne od rozkładu danych.
3.2 Sortowanie pozycyjne (Radix Sort)
- Idea: sortowanie według kolejnych cyfr/liczb znaczących.
- Złożoność: O(nk), gdzie k to liczba cyfr.
- Zalety: bardzo szybkie dla liczb całkowitych.
- Wady: ograniczone zastosowanie (nie działa bezpośrednio na wszystkich typach danych).
4. Porównanie algorytmów sortowania
| Algorytm | Najlepszy przypadek | Średni przypadek | Najgorszy przypadek | Pamięć dodatkowa |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) |
Porównanie złożoności obliczeniowej
Wizualizacja teoretycznych złożoności: O(n), O(n log n), O(n²). Możesz przełączać konkretne algorytmy.
Włącz/wyłącz algorytmy
Algorytmy zaawansowane
Legenda i wskazówki
Tutaj wykres przedstawia krzywe znormalizowane (domyślnie). Możesz zmienić Maksymalny rozmiar n, przełączyć skalę osi Y na logarytmiczną, lub wyłączyć normalizację, by zobaczyć surowe kształty krzywych.
- O(n²) — algorytmy proste (bardzo strome dla dużych n).
- O(n log n) — algorytmy efektywne dostępne w standardowych bibliotekach.
- Pobierz wykres przyciskiem, aby dołączyć go do dokumentacji.
Wizualizacja algorytmów sortowania
Kolor czerwony oznacza aktualnie porównywane / zamieniane elementy.
5. Podsumowanie
Wybór algorytmu sortowania zależy od rodzaju danych oraz dostępnych zasobów.
- Dla małych zbiorów – dobrze sprawdzają się algorytmy proste (np. Insertion Sort).
- Dla dużych zbiorów ogólnych – najlepszy wybór to Quick Sort lub Merge Sort.
- Dla danych liczbowych o ograniczonym zakresie – skuteczny będzie Radix Sort lub Bucket Sort.
- Gdy ważne jest zużycie pamięci – najlepszy będzie Heap Sort.
18 września 2025
1