Algorytmy sortowania - Klasyfikacja gatunków

Witaj ponownie, @name! Darwin tutaj z kolejną kluczową umiejętnością.

Wyobraź sobie, że odkryłeś/aś 100 różnych gatunków podczas ekspedycji. Musisz je uporządkować alfabetycznie do katalogu. Jak to zrobisz? Możesz:

• Bąbelkować - porównywać sąsiednie, zamieniać miejscami (powoli, ale prosto)
• Wybierać - znajdować najmniejszego, dodawać do nowej listy (też powoli)
• Dzielić i łączyć - rozdzielić na połowy, posortować osobno, scalić (szybko!)

To są właśnie algorytmy sortowania - różne sposoby porządkowania danych. Każdy ma swoje zalety, wady i złożoność!

Dlaczego sortowanie jest ważne?

Posortowane dane pozwalają na:

• ✅ Szybsze wyszukiwanie - binary search wymaga posortowanych danych
• ✅ Łatwiejsze analizowanie - łatwo znaleźć min/max, medianę
• ✅ Lepszą prezentację - alfabetycznie, chronologicznie
• ✅ Efektywność - wiele algorytmów działa lepiej na posortowanych danych

1# Przykład: Szukanie w posortowanej liście
2species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
3
4# Binary search - O(log n) - ale wymaga sortowania!
5import bisect
6index = bisect.bisect_left(species, "Leo")  # Szybkie!
7
8# vs niepodortowana lista - O(n)
9unsorted_species = ["Python", "Leo", "Gorilla", ...]
10index = unsorted_species.index("Leo")  # Wolniejsze dla dużych list

Python's built-in sort

Python ma wbudowane sortowanie - Timsort (hybrydowy merge sort + insertion sort).

1# 1. list.sort() - sortuje in-place (modyfikuje oryginalną listę)
2animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
3animals.sort()  # Modyfikuje animals
4print(animals)  # ['Lew', 'Papuga', 'Słoń', 'Tygrys']
5
6# 2. sorted() - zwraca nową posortowaną listę
7animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
8sorted_animals = sorted(animals)  # Nowa lista
9print(animals)  # ['Tygrys', 'Słoń', 'Lew', 'Papuga'] - niezmienione
10print(sorted_animals)  # ['Lew', 'Papuga', 'Słoń', 'Tygrys']
11
12# 3. Sortowanie z kluczem
13animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
14sorted_by_length = sorted(animals, key=len)
15print(sorted_by_length)  # ['Lew', 'Słoń', 'Tygrys', 'Papuga']
16
17# 4. Odwrotne sortowanie
18animals.sort(reverse=True)
19print(animals)  # ['Tygrys', 'Słoń', 'Papuga', 'Lew']
20
21# 5. Sortowanie dict po wartościach
22species_count = {"Python": 5, "Leo": 3, "Elephas": 8}
23sorted_species = sorted(species_count.items(), key=lambda x: x[1], reverse=True)
24print(sorted_species)  # [('Elephas', 8), ('Python', 5), ('Leo', 3)]

Złożoność Timsort: O(n log n) w najgorszym przypadku, O(n) w najlepszym

Ale zrozumienie klasycznych algorytmów sortowania pomoże Ci:

• Zrozumieć jak działa sortowanie "pod maską"
• Rozwiązywać interview questions
• Wybrać odpowiedni algorytm dla specyficznych przypadków

Bubble Sort - Sortowanie bąbelkowe

Idea: Porównuj sąsiednie elementy i zamieniaj je miejscami, jeśli są w złej kolejności. Powtarzaj, aż wszystko będzie posortowane.

Analogia Safari: Jak bąbelki powietrza w wodzie - lżejsze (mniejsze) elementy "wypływają" na górę.

1def bubble_sort(arr):
2    """
3    Sortowanie bąbelkowe - O(n²)
4
5    Algorytm:
6    1. Przejdź przez całą listę
7    2. Porównaj każdą parę sąsiednich elementów
8    3. Zamień je miejscami, jeśli są w złej kolejności
9    4. Powtarzaj, aż nic się nie zmienia
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # Po każdej iteracji największy element "wypłynie" na koniec
15        swapped = False  # Optymalizacja - jeśli nic nie zmieniliśmy, lista jest posortowana
16
17        for j in range(0, n - i - 1):  # Pomijamy ostatnie i elementów (już posortowane)
18            if arr[j] > arr[j + 1]:
19                # Zamiana miejscami
20                arr[j], arr[j + 1] = arr[j + 1], arr[j]
21                swapped = True
22
23        if not swapped:
24            break  # Lista już posortowana
25
26    return arr
27
28# Przykład
29species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
30sorted_species = bubble_sort(species.copy())
31print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
32
33# Krok po kroku:
34# Pass 1: ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python "wypłynął"
35# Pass 2: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera "wypłynęła"
36# Pass 3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Już posortowane

Złożoność:

• Czas: O(n²) najgorszy i średni, O(n) najlepszy (dla już posortowanej listy)
• Pamięć: O(1) - sortuje in-place
• Stabilny: Tak - zachowuje kolejność równych elementów

Zalety: Prosty, stabilny, dobry dla małych danych lub prawie posortowanych Wady: Bardzo wolny dla dużych danych - O(n²)

Selection Sort - Sortowanie przez wybieranie

Idea: Znajdź najmniejszy element i wstaw na początek. Znajdź drugi najmniejszy i wstaw na drugą pozycję. Powtarzaj.

Analogia Safari: Wybieranie najmniejszych gatunków po kolei do posortowanego katalogu.

1def selection_sort(arr):
2    """
3    Sortowanie przez wybieranie - O(n²)
4
5    Algorytm:
6    1. Znajdź najmniejszy element w nieposortowanej części
7    2. Zamień go z pierwszym elementem nieposortowanej części
8    3. Przesuń granicę posortowanej części o 1
9    4. Powtarzaj
10    """
11    n = len(arr)
12
13    for i in range(n):
14        # Znajdź index najmniejszego elementu w nieposortowanej części
15        min_index = i
16        for j in range(i + 1, n):
17            if arr[j] < arr[min_index]:
18                min_index = j
19
20        # Zamień najmniejszy element z pierwszym nieposortowanym
21        arr[i], arr[min_index] = arr[min_index], arr[i]
22
23    return arr
24
25# Przykład
26species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
27sorted_species = selection_sort(species.copy())
28print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
29
30# Krok po kroku:
31# i=0: ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]  # Znaleziono min: Elephas
32# i=1: ["Elephas", "Gorilla", "Python", "Leo", "Panthera"]  # Znaleziono min: Gorilla
33# i=2: ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]  # Znaleziono min: Leo
34# i=3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Znaleziono min: Panthera
35# i=4: Done

Złożoność:

• Czas: O(n²) zawsze - nawet dla posortowanej listy!
• Pamięć: O(1) - sortuje in-place
• Stabilny: Nie - może zmienić kolejność równych elementów

Zalety: Prosty, przewidywalny czas, mało zamian Wady: Wolny - zawsze O(n²), niestabilny

Insertion Sort - Sortowanie przez wstawianie

Idea: Buduj posortowaną listę element po elemencie, wstawiając każdy nowy element na właściwe miejsce.

Analogia Safari: Jak układanie kart w ręce - bierzesz kartę i wstawiasz ją w odpowiednie miejsce.

1def insertion_sort(arr):
2    """
3    Sortowanie przez wstawianie - O(n²)
4
5    Algorytm:
6    1. Zacznij od drugiego elementu
7    2. Porównaj go z elementami z lewej strony
8    3. Przesuń większe elementy w prawo
9    4. Wstaw element na właściwe miejsce
10    5. Powtarzaj dla każdego elementu
11    """
12    for i in range(1, len(arr)):
13        key = arr[i]  # Element do wstawienia
14        j = i - 1
15
16        # Przesuń elementy większe niż key o jedną pozycję w prawo
17        while j >= 0 and arr[j] > key:
18            arr[j + 1] = arr[j]
19            j -= 1
20
21        # Wstaw key na właściwe miejsce
22        arr[j + 1] = key
23
24    return arr
25
26# Przykład
27species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
28sorted_species = insertion_sort(species.copy())
29print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
30
31# Krok po kroku:
32# i=1 (Leo):      ["Leo", "Python", "Elephas", "Gorilla", "Panthera"]
33# i=2 (Elephas):  ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]
34# i=3 (Gorilla):  ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]
35# i=4 (Panthera): ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]

Złożoność:

• Czas: O(n²) najgorszy i średni, O(n) najlepszy (dla prawie posortowanej)
• Pamięć: O(1) - sortuje in-place
• Stabilny: Tak

Zalety: Prosty, stabilny, świetny dla małych lub prawie posortowanych danych, online (może sortować w trakcie otrzymywania danych) Wady: Wolny dla dużych nieuporządkowanych danych - O(n²)

Timsort używa insertion sort dla małych podlist (<64 elementy)!

Merge Sort - Sortowanie przez scalanie

Idea: Dziel listę na połowy, sortuj rekurencyjnie, scalaj posortowane połówki.

Analogia Safari: Dziel zespół na mniejsze grupy, każda grupa sortuje osobno, potem łączysz wyniki.

1def merge_sort(arr):
2    """
3    Sortowanie przez scalanie - O(n log n)
4
5    Algorytm (Divide and Conquer):
6    1. Jeśli lista ma 1 element - już posortowana
7    2. Podziel listę na dwie połowy
8    3. Posortuj każdą połowę rekurencyjnie
9    4. Scal dwie posortowane połówki
10    """
11    if len(arr) <= 1:
12        return arr
13
14    # Dziel
15    mid = len(arr) // 2
16    left = merge_sort(arr[:mid])
17    right = merge_sort(arr[mid:])
18
19    # Scalaj
20    return merge(left, right)
21
22def merge(left, right):
23    """
24    Scal dwie posortowane listy w jedną posortowaną listę
25    """
26    result = []
27    i = j = 0
28
29    # Porównuj elementy z obu list i dodawaj mniejszy
30    while i < len(left) and j < len(right):
31        if left[i] <= right[j]:
32            result.append(left[i])
33            i += 1
34        else:
35            result.append(right[j])
36            j += 1
37
38    # Dodaj pozostałe elementy (jedna z list jest pusta)
39    result.extend(left[i:])
40    result.extend(right[j:])
41
42    return result
43
44# Przykład
45species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
46sorted_species = merge_sort(species)
47print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']
48
49# Drzewo rekurencji:
50# ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
51#       /                                  \
52# ["Python", "Leo"]                  ["Elephas", "Gorilla", "Panthera"]
53#   /        \                           /                \
54# ["Python"] ["Leo"]               ["Elephas"]    ["Gorilla", "Panthera"]
55#                                                      /            \
56#                                                ["Gorilla"]    ["Panthera"]
57# Scalanie:
58# ["Leo", "Python"]                 ["Elephas", "Gorilla", "Panthera"]
59#                \                    /
60#         ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Złożoność:

• Czas: O(n log n) zawsze - najgorszy, średni, najlepszy
• Pamięć: O(n) - tworzy nowe listy podczas scalania
• Stabilny: Tak

Zalety: Przewidywalny O(n log n), stabilny, dobry dla dużych danych Wady: Używa dodatkowej pamięci O(n)

Quick Sort - Sortowanie szybkie

Idea: Wybierz pivot, podziel listę na mniejsze i większe od pivot, sortuj rekurencyjnie każdą część.

Analogia Safari: Wybierz "medianowego" gatunku, podziel na mniejsze i większe, powtarzaj.

1def quick_sort(arr):
2    """
3    Sortowanie szybkie - O(n log n) średnio, O(n²) najgorszy
4
5    Algorytm:
6    1. Jeśli lista ma ≤1 element - już posortowana
7    2. Wybierz pivot (np. ostatni element)
8    3. Podziel na: mniejsze od pivot, równe pivot, większe od pivot
9    4. Posortuj rekurencyjnie mniejsze i większe
10    5. Połącz: [posortowane mniejsze] + [pivot] + [posortowane większe]
11    """
12    if len(arr) <= 1:
13        return arr
14
15    # Wybierz pivot (np. ostatni element)
16    pivot = arr[-1]
17
18    # Podziel na 3 grupy
19    smaller = [x for x in arr[:-1] if x < pivot]
20    equal = [x for x in arr if x == pivot]
21    larger = [x for x in arr[:-1] if x > pivot]
22
23    # Rekurencyjnie posortuj i połącz
24    return quick_sort(smaller) + equal + quick_sort(larger)
25
26# Bardziej efektywna wersja (in-place):
27def quick_sort_inplace(arr, low=0, high=None):
28    """Quick sort in-place z partycjonowaniem Lomuto"""
29    if high is None:
30        high = len(arr) - 1
31
32    if low < high:
33        # Partycjonuj i otrzymaj index pivota
34        pivot_index = partition(arr, low, high)
35
36        # Posortuj części przed i po pivocie
37        quick_sort_inplace(arr, low, pivot_index - 1)
38        quick_sort_inplace(arr, pivot_index + 1, high)
39
40    return arr
41
42def partition(arr, low, high):
43    """Partycjonowanie Lomuto"""
44    pivot = arr[high]  # Wybierz ostatni element jako pivot
45    i = low - 1  # Index mniejszego elementu
46
47    for j in range(low, high):
48        if arr[j] <= pivot:
49            i += 1
50            arr[i], arr[j] = arr[j], arr[i]
51
52    # Umieść pivot na właściwym miejscu
53    arr[i + 1], arr[high] = arr[high], arr[i + 1]
54    return i + 1
55
56# Przykład
57species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
58sorted_species = quick_sort(species)
59print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

Złożoność:

• Czas: O(n log n) średnio, O(n²) najgorszy (gdy pivot zawsze najgorszy)
• Pamięć: O(log n) rekurencja (in-place wersja)
• Stabilny: Nie (standardowa implementacja)

Zalety: Bardzo szybki w praktyce, sortuje in-place (mała pamięć) Wady: Niestabilny, O(n²) w najgorszym przypadku, wymaga dobrego wyboru pivot

Porównanie algorytmów sortowania

| Algorytm | Najlepszy | Średni | Najgorszy | Pamięć | Stabilny | |----------|-----------|--------|-----------|--------|----------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Tak | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ Nie | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Tak | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Tak | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ Nie | | Python sort() | O(n) | O(n log n) | O(n log n) | O(n) | ✅ Tak |

Kiedy używać którego algorytmu?

1# Małe dane (<50 elementów) lub prawie posortowane
2# → Insertion Sort
3small_list = ["Python", "Leo", "Elephas"]
4insertion_sort(small_list)  # Szybkie dla małych danych!
5
6# Duże dane, potrzebujesz stabilności
7# → Merge Sort lub Python sort()
8large_list = [random.random() for _ in range(10000)]
9sorted_list = sorted(large_list)  # Timsort - stabilny!
10
11# Duże dane, pamięć ograniczona, nie potrzebujesz stabilności
12# → Quick Sort (in-place)
13large_list = [random.random() for _ in range(10000)]
14quick_sort_inplace(large_list)  # Mało pamięci!
15
16# W praktyce: ZAWSZE używaj Python sort() lub sorted()
17# Są zoptymalizowane, stabilne i bardzo szybkie (Timsort)!
18animals.sort()  # Najlepszy wybór w 99% przypadków!

Sortowanie własnych obiektów

1# Safari przykład: Sortowanie gatunków po różnych kryteriach
2
3class Species:
4    def __init__(self, name, size, dangerous):
5        self.name = name
6        self.size = size  # metry
7        self.dangerous = dangerous
8
9species_list = [
10    Species("Python regius", 1.5, False),
11    Species("Panthera leo", 2.5, True),
12    Species("Elephas maximus", 3.5, False),
13    Species("Crocodylus niloticus", 4.5, True),
14    Species("Gorilla gorilla", 1.8, False)
15]
16
17# 1. Sortowanie po nazwie
18sorted_by_name = sorted(species_list, key=lambda s: s.name)
19for s in sorted_by_name:
20    print(s.name)
21# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius
22
23# 2. Sortowanie po rozmiarze (malejąco)
24sorted_by_size = sorted(species_list, key=lambda s: s.size, reverse=True)
25for s in sorted_by_size:
26    print(f"{s.name}: {s.size}m")
27# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...
28
29# 3. Sortowanie po niebezpieczeństwie, potem rozmiarze
30sorted_by_danger_size = sorted(species_list, key=lambda s: (not s.dangerous, -s.size))
31for s in sorted_by_danger_size:
32    danger = "⚠️" if s.dangerous else "✓"
33    print(f"{danger} {s.name}: {s.size}m")
34# ⚠️ Crocodylus niloticus: 4.5m (dangerous + largest)
35# ⚠️ Panthera leo: 2.5m (dangerous)
36# ✓ Elephas maximus: 3.5m (safe + large)
37# ...

Counting Sort - dla specjalnych przypadków

Jeśli sortujemy liczby całkowite z ograniczonego zakresu, możemy użyć Counting Sort - O(n + k)!

1def counting_sort(arr, max_value):
2    """
3    Counting sort - O(n + k) gdzie k = max_value
4
5    Działa tylko dla liczb całkowitych z zakresu [0, max_value]
6    """
7    # Zlicz wystąpienia każdej liczby
8    count = [0] * (max_value + 1)
9    for num in arr:
10        count[num] += 1
11
12    # Zbuduj posortowaną listę
13    sorted_arr = []
14    for num, freq in enumerate(count):
15        sorted_arr.extend([num] * freq)
16
17    return sorted_arr
18
19# Safari przykład: Sortowanie liczby odkryć (0-100)
20daily_discoveries = [5, 3, 8, 3, 12, 5, 7, 3, 10, 5]
21sorted_discoveries = counting_sort(daily_discoveries, max(daily_discoveries))
22print(sorted_discoveries)  # [3, 3, 3, 5, 5, 5, 7, 8, 10, 12]
23
24# O(n) dla ograniczonego zakresu! Szybsze niż O(n log n) dla dużych n!

Praktyczny przykład - System katalogowania

1class SpeciesCatalog:
2    """System katalogowania gatunków z różnymi sortowaniami"""
3
4    def __init__(self):
5        self.species = []
6
7    def add_species(self, name, size, habitat, dangerous):
8        """Dodaj gatunek do katalogu"""
9        self.species.append({
10            "name": name,
11            "size": size,
12            "habitat": habitat,
13            "dangerous": dangerous
14        })
15
16    def sort_by_name(self):
17        """Sortuj alfabetycznie"""
18        return sorted(self.species, key=lambda s: s["name"])
19
20    def sort_by_size(self, descending=True):
21        """Sortuj po rozmiarze"""
22        return sorted(self.species, key=lambda s: s["size"], reverse=descending)
23
24    def sort_by_danger_then_size(self):
25        """Sortuj: niebezpieczne najpierw, potem po rozmiarze"""
26        return sorted(self.species, key=lambda s: (not s["dangerous"], -s["size"]))
27
28    def filter_and_sort(self, habitat=None, min_size=None, sort_by="name"):
29        """Filtruj i sortuj"""
30        filtered = self.species
31
32        if habitat:
33            filtered = [s for s in filtered if s["habitat"] == habitat]
34
35        if min_size:
36            filtered = [s for s in filtered if s["size"] >= min_size]
37
38        if sort_by == "name":
39            return sorted(filtered, key=lambda s: s["name"])
40        elif sort_by == "size":
41            return sorted(filtered, key=lambda s: s["size"], reverse=True)
42
43        return filtered
44
45# Użycie
46catalog = SpeciesCatalog()
47catalog.add_species("Python regius", 1.5, "jungle", False)
48catalog.add_species("Panthera leo", 2.5, "savanna", True)
49catalog.add_species("Elephas maximus", 3.5, "jungle", False)
50catalog.add_species("Crocodylus niloticus", 4.5, "river", True)
51
52# Duże gatunki z dżungli, posortowane po rozmiarze
53jungle_large = catalog.filter_and_sort(habitat="jungle", min_size=2.0, sort_by="size")
54for s in jungle_large:
55    print(f"{s['name']}: {s['size']}m")
56# Elephas maximus: 3.5m

Zadanie praktyczne

Napisz funkcję sortującą ekspedycje po:

1. Liczbie odkrytych gatunków (malejąco)
2. Całkowitym dystansie (rosnąco)
3. Średniej temperaturze (malejąco)

Porównaj wydajność różnych algorytmów dla 100, 1000, 10000 elementów.

Podsumowanie

W tej lekcji nauczyłeś/aś się:

• ✅ Dlaczego sortowanie jest ważne
• ✅ Python's built-in sort() i sorted()
• ✅ Bubble Sort, Selection Sort, Insertion Sort (O(n²))
• ✅ Merge Sort i Quick Sort (O(n log n))
• ✅ Porównania algorytmów sortowania
• ✅ Kiedy używać którego algorytmu
• ✅ Sortowania własnych obiektów z key
• ✅ Counting Sort dla specjalnych przypadków

Checkpoint

Przed przejściem dalej:

• [ ] Rozumiesz jak działają podstawowe algorytmy sortowania
• [ ] Znasz różnicę między O(n²) a O(n log n) algorytmami
• [ ] Potrafisz użyć sort() i sorted() z parametrem key
• [ ] Wiesz kiedy używać stabilnego sortowania
• [ ] Rozumiesz trade-off między czasem a pamięcią
• [ ] Potrafisz wybrać odpowiedni algorytm dla danej sytuacji

W praktyce: Używaj Python's sort() lub sorted() - są zoptymalizowane i działają świetnie w 99% przypadków!

W następnej lekcji Darwin wprowadzi Cię w stosy i kolejki - struktury do organizacji ekspedycji! 📚🔄