Wprowadzenie do sortowania
1. Czym jest sortowanie?
Sortowanie to proces uporządkowania elementów według określonego kryterium (najczęściej rosnąco lub malejąco).
Przykład:
Lista nieposortowana: [64, 34, 25, 12, 22, 11, 90]
Lista posortowana: [11, 12, 22, 25, 34, 64, 90]
2. Po co sortować?
2.1. Szybsze wyszukiwanie
Nieposortowana lista – wyszukiwanie liniowe O(n):
Posortowana lista – wyszukiwanie binarne O(log n):
Dla 1,000,000 elementów: - Liniowe: 1,000,000 porównań - Binarne: ~20 porównań
2.2. Łatwiejsze znajdowanie duplikatów
2.3. Znajdujemy medianę
2.4. Praktyczne zastosowania
- Wyniki wyszukiwarek (sortowanie po relevance)
- E-commerce (sortowanie po cenie, popularności)
- Social media (sortowanie postów po czasie)
- Bazy danych (ORDER BY)
- Kompresja danych
- Algorytmy grafowe (Kruskal, Dijkstra)
3. Podstawowe terminy
3.1. Sortowanie rosnące vs malejące
3.2. Sortowanie stabilne vs niestabilne
Stabilne: Zachowuje kolejność elementów o tej samej wartości
Przed: [(1, 'a'), (3, 'b'), (1, 'c'), (2, 'd')]
Po (stabilne): [(1, 'a'), (1, 'c'), (2, 'd'), (3, 'b')]
↑ ↑
Kolejność zachowana!
Niestabilne: Może zmienić kolejność równych elementów
Przed: [(1, 'a'), (3, 'b'), (1, 'c'), (2, 'd')]
Po (niestabilne): [(1, 'c'), (1, 'a'), (2, 'd'), (3, 'b')]
↑ ↑
Kolejność MOŻE się zmienić
3.3. In-place vs out-of-place
In-place: Sortuje używając stałej ilości dodatkowej pamięci O(1)
Out-of-place: Używa dodatkowej pamięci O(n)
3.4. Porównaniowe vs nie-porównaniowe
Porównaniowe: Sortuje przez porównywanie elementów (<, >, ==)
- Przykłady: bubble sort, merge sort, quick sort
- Dolne ograniczenie: Ω(n log n)
Nie-porównaniowe: Wykorzystuje właściwości danych (np. zakres wartości) - Przykłady: counting sort, radix sort, bucket sort - Może być szybsze niż O(n log n) dla specyficznych danych!
4. Klasyfikacja algorytmów sortowania
| Algorytm | Najlepszy | Średni | Najgorszy | Pamięć | Stabilny |
|---|---|---|---|---|---|
| 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) | ❌ |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | ✅ |
5. Sortowanie w Pythonie
5.1. Metoda sort() – in-place
Złożoność: O(n log n) – używa Timsort
5.2. Funkcja sorted() – zwraca nową listę
5.3. Sortowanie z kluczem
5.4. Sortowanie obiektów
6. Mierzenie wydajności sortowania
7. Wizualizacja sortowania
Przykład – animacja bubble sort
8. Kiedy używać którego algorytmu?
8.1. Małe dane (n < 50)
✅ Insertion Sort - Prosty w implementacji - Dobry dla prawie posortowanych danych - Niski overhead
8.2. Średnie/duże dane (n > 50)
✅ Quick Sort (średnio najszybszy) - O(n log n) średnio - In-place (mało pamięci) - Cache-friendly
✅ Merge Sort (gwarantowana wydajność) - O(n log n) zawsze - Stabilny - Wymaga O(n) pamięci
8.3. Dane prawie posortowane
✅ Insertion Sort lub Bubble Sort - O(n) dla już posortowanych - Adaptywne
8.4. Potrzebujesz stabilności
✅ Merge Sort ✅ Timsort (Python default)
8.5. Ograniczona pamięć
✅ Heap Sort - O(n log n) zawsze - In-place O(1) pamięci
9. Dolne ograniczenie sortowania porównaniowego
Twierdzenie: Każdy algorytm sortowania oparty na porównaniach wymaga co najmniej Ω(n log n) porównań w najgorszym przypadku.
Dowód (intuicja):
Dla n elementów istnieje n! możliwych permutacji.
Każde porównanie dzieli zbiór możliwości na 2 części (tak/nie).
Potrzebujemy drzewa decyzyjnego o n! liściach.
Wysokość takiego drzewa: log₂(n!) ≈ n log n
Wniosek: Algorytmy O(n log n) są optymalne dla sortowania porównaniowego!
10. Przykłady zastosowań
10.1. Top K elementów
10.2. Sortowanie po wielu kluczach
10.3. Znajdowanie anagramów
11. Timsort – algorytm Pythona
Timsort to hybrydowy algorytm sortowania używany w Pythonie (od wersji 2.3).
Cechy:
- Hybrydowy: Łączy insertion sort i merge sort
- Adaptywny: Wykorzystuje już posortowane fragmenty
- Stabilny: Zachowuje kolejność równych elementów
- Złożoność: O(n log n) najgorsza, O(n) najlepsza
Dlaczego Timsort?
12. Ćwiczenia
Zadanie 1: Czy lista jest posortowana?
Rozwiązanie
Zadanie 2: Sortuj string
13. Podsumowanie
Sortowanie:
- Proces uporządkowania elementów
- Kluczowe dla wydajnych algorytmów
- Dolne ograniczenie porównaniowe: Ω(n log n)
- Python używa Timsort – O(n log n)
Kluczowe pojęcia:
- Stabilność – zachowanie kolejności równych elementów
- In-place – O(1) dodatkowej pamięci
- Adaptywność – szybsze dla prawie posortowanych
Kategorie algorytmów:
| Kategoria | Złożoność | Przykłady |
|---|---|---|
| Wolne (O(n²)) | Małe dane | Bubble, Selection, Insertion |
| Szybkie (O(n log n)) | Ogólne | Merge, Quick, Heap |
| Specjalne | Zależy | Counting, Radix, Bucket |
Wybór algorytmu:
- Małe dane: Insertion Sort
- Ogólne: Quick Sort lub Python
sorted() - Gwarantowana wydajność: Merge Sort lub Heap Sort
- Stabilność: Merge Sort lub Timsort
Co dalej warto poznać:
- Szczegóły każdego algorytmu
- Implementacje od zera
- Optymalizacje (hybrydy)
- Sortowanie nieparównaniowe