Porównanie algorytmów sortowania

1. Tabela porównawcza

Algorytm Najlepszy Średni Najgorszy Pamięć Stabilny In-place
Bubble Sort O(n) O(n²) O(n²) O(1) ✅ ✅
Selection Sort O(n²) O(n²) O(n²) O(1) ❌ ✅
Insertion Sort O(n) O(n²) O(n²) O(1) ✅ ✅
Merge Sort O(n log n) O(n log n) O(n log n) O(n) ✅ ❌
Quick Sort O(n log n) O(n log n) O(n²) O(log n) ❌ ✅
Heap Sort O(n log n) O(n log n) O(n log n) O(1) ❌ ✅

2. Kategorie algorytmów

2.1. Proste (O(n²)) – dla małych danych

Kiedy używać: - n < 50 – insertion sort najlepszy - Prawie posortowane – insertion/bubble (O(n)!) - Edukacja – najprostsze do zrozumienia

2.2. Zaawansowane (O(n log n)) – dla dużych danych

Kiedy używać: - Ogólne – quick sort (najszybszy średnio) - Gwarantowana wydajność – merge/heap sort - Stabilność – merge sort - Mało pamięci – heap sort

3. Szczegółowe porównania

3.1. Bubble vs Selection vs Insertion

Wynik:

n=500:
  Bubble:    0.0512s
  Selection: 0.0321s
  Insertion: 0.0245s (najszybszy!)

Wnioski: 1. Insertion > Selection > Bubble dla losowych danych 2. Dla prawie posortowanych: Insertion >> Selection >> Bubble 3. Selection ma najmniej zamian O(n)

3.2. Merge vs Quick vs Heap

Wynik:

n=10000:
  Merge:  0.0891s
  Quick:  0.0512s (najszybszy!)
  Heap:   0.1234s
  Python: 0.0038s (Timsort)

Wnioski: 1. Quick > Merge > Heap dla losowych danych 2. Python Timsort najszybszy (hybrydowy, zoptymalizowany w C) 3. Heap najwolniejszy (gorsze cache locality)

4. Charakterystyki algorytmów

4.1. Stabilność

Stabilne (zachowują kolejność równych): - ✅ Bubble Sort - ✅ Insertion Sort - ✅ Merge Sort

Niestabilne: - ❌ Selection Sort - ❌ Quick Sort - ❌ Heap Sort

Przykład:

4.2. Adaptywność

Adaptywne (szybsze dla prawie posortowanych): - ✅ Bubble Sort (z optymalizacją) - ✅ Insertion Sort

Nie-adaptywne: - ❌ Selection Sort (zawsze O(n²)) - ❌ Merge Sort (zawsze O(n log n)) - ❌ Quick Sort (bez optymalizacji) - ❌ Heap Sort (zawsze O(n log n))

4.3. Pamięć (in-place vs out-of-place)

In-place O(1): - ✅ Bubble Sort - ✅ Selection Sort - ✅ Insertion Sort - ✅ Quick Sort (O(log n) dla rekurencji) - ✅ Heap Sort

Out-of-place O(n): - ❌ Merge Sort (wymaga dodatkowej tablicy)

5. Drzewo decyzyjne – kiedy którego użyć?

Czy n < 50?
├─ TAK → Insertion Sort (prosty, szybki dla małych)
└─ NIE → Czy potrzebujesz stabilności?
         ├─ TAK → Merge Sort (gwarantowana stabilność)
         └─ NIE → Czy pamięć ograniczona?
                  ├─ TAK → Czy gwarantowana wydajność?
                  │        ├─ TAK → Heap Sort (O(1) pamięci + O(n log n))
                  │        └─ NIE → Quick Sort (najszybszy średnio)
                  └─ NIE → Quick Sort (najszybszy średnio)

Praktyczne wskazówki:

6. Najgorsze przypadki

6.1. Bubble/Selection/Insertion: O(n²)

6.2. Quick Sort: O(n²)

6.3. Merge Sort: O(n log n) zawsze ✅

6.4. Heap Sort: O(n log n) zawsze ✅

7. Benchmark wszystkich algorytmów

Przykładowe wyniki:

--- 100 elementów (losowe) ---
Python sorted  : 0.000018s
Quick          : 0.000089s
Insertion      : 0.000124s
Merge          : 0.000156s
Selection      : 0.000198s
Heap           : 0.000234s
Bubble         : 0.000289s

Najszybszy: Python sorted

--- 1000 elementów (losowe) ---
Python sorted  : 0.000201s
Quick          : 0.002134s
Heap           : 0.008912s
Merge          : 0.009456s
Insertion      : 0.012456s
Selection      : 0.032145s
Bubble         : 0.051234s

Najszybszy: Python sorted

8. Timsort – algorytm Pythona

Timsort to hybrydowy algorytm używany w Python sorted() i list.sort():

Cechy:

  • Hybrydowy: Łączy insertion sort + merge sort
  • Adaptywny: O(n) dla prawie posortowanych, O(n log n) najgorsza
  • Stabilny: Zachowuje kolejność równych
  • Zoptymalizowany: Napisany w C, bardzo szybki

Strategia:

Dlaczego najszybszy? - Wykorzystuje naturalne "runs" (już posortowane fragmenty) - Insertion sort dla małych fragmentów (niski overhead) - Zoptymalizowany w C (nie w Pythonie)

9. Podsumowanie – który wybrać?

🏆 Top 3 rekomendacje:

1. Python sorted() / .sort() (Timsort)

Dlaczego: - Najszybszy (napisany w C) - Stabilny - Adaptywny - Przetestowany w milionach projektów

2. Insertion Sort – małe dane

Dlaczego: - Prosty - Bardzo szybki dla małych danych - O(n) dla prawie posortowanych - Stabilny

3. Quick Sort – gdy implementujesz od zera

Dlaczego: - Najszybszy średnio (po Timsort) - In-place - Relatywnie prosty

Tabela decyzyjna:

Sytuacja Algorytm Dlaczego
Produkcja (Python) sorted() / .sort() Najszybszy, stabilny, testowany
Małe dane (n < 50) Insertion Sort Prosty, szybki dla małych
Prawie posortowane Insertion Sort O(n)!
Gwarantowana wydajność Heap Sort / Merge Sort Zawsze O(n log n)
Stabilność wymagana Merge Sort Stabilny + O(n log n)
Mało pamięci + gwarancja Heap Sort O(1) pamięci + O(n log n)
Ogólne (implementacja ręczna) Quick Sort (losowy) Najszybszy średnio
Edukacja Bubble/Insertion Najprostsze do zrozumienia

10. Najważniejsze wnioski

✅ DO:

  1. Używaj sorted() w Pythonie – zawsze najlepszy wybór
  2. Insertion sort dla n < 50 – prosty i szybki
  3. Quick sort dla ogólnych przypadków (z losowym pivotem)
  4. Heap sort gdy pamięć ograniczona + gwarantowana wydajność

❌ DON'T:

  1. NIE używaj bubble/selection sort w produkcji (tylko edukacja)
  2. NIE implementuj własnego sortowania bez powodu (użyj sorted())
  3. NIE używaj quick sort bez optymalizacji (losowy pivot!)
  4. NIE ignoruj stabilności jeśli sortowanie wielokrotne

11. Co dalej warto poznać?

Zaawansowane algorytmy:

  1. Timsort – szczegóły implementacji
  2. Introsort – hybrydowy (quick + heap + insertion)
  3. Counting Sort – O(n+k) dla ograniczonego zakresu
  4. Radix Sort – O(nk) dla liczb
  5. Bucket Sort – O(n) średnio dla równomiernego rozkładu

Specjalne zastosowania:

  1. External Merge Sort – sortowanie dużych plików
  2. Parallel Sorting – sortowanie wielowątkowe
  3. GPU Sorting – sortowanie na karcie graficznej
  4. String Sorting – specjalne algorytmy dla stringów

Struktury danych:

  1. Heap (kopiec) – podstawa heap sort i priority queue
  2. Balanced Trees – AVL, Red-Black (sortowanie w O(n log n))
  3. Skip Lists – probabilistyczna alternatywa dla drzew

12. Przykład praktyczny – sortowanie w aplikacji

Dlaczego sorted()? - Stabilny – Anna przed Piotr (oboje score=95, Anna młodsza) - Szybki – Timsort O(n log n) - Prosty – jedna linijka kodu!

Końcowa rada: W Pythonie ZAWSZE używaj sorted() lub .sort() chyba że masz bardzo konkretny powód, żeby implementować własny algorytm!

Wróć do spisu lekcji