Algorytmy sortowania - Klasyfikacja gatunków

Witaj ponownie! 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 nieposortowana lista - O(n)
9unsorted_species = ["Python", "Leo", "Gorilla", ...]
10index = unsorted_species.index("Leo")  # Wolniejsze dla dużych list

Wyszukiwanie binarne - po co nam posortowany katalog

Posortowana lista pozwala szukać sprytniej niż wpis po wpisie. Wyszukiwanie binarne (binary search) działa jak szukanie gatunku w papierowym atlasie: otwierasz go w połowie i od razu wiesz, w której części szukać dalej. Każda runda powtarza te same cztery kroki:

1. Znajdź środkowy element przeszukiwanego zakresu.
2. Porównaj go z szukaną wartością.
3. Jeśli to nie on, wybierz lewą albo prawą połowę - tę, w której szukana wartość może się jeszcze znajdować.
4. Powtarzaj na coraz mniejszym zakresie, aż znajdziesz element albo zakres się skończy - wtedy zwróć wynik.

1def binary_search(sorted_list, target):
2    left = 0
3    right = len(sorted_list) - 1
4    while left <= right:
5        mid = (left + right) // 2       # 1. środek zakresu
6        if sorted_list[mid] == target:  # 2. porównanie
7            return mid                  # 4. znaleziono - zwróć pozycję
8        elif sorted_list[mid] < target:
9            left = mid + 1              # 3. szukaj w prawej połowie
10        else:
11            right = mid - 1             # 3. szukaj w lewej połowie
12    return -1                           # 4. nie znaleziono
13
14species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
15print(binary_search(species, "Leo"))  # 2

Lista musi być posortowana - inaczej porównanie ze środkiem nic nie mówi o tym, w której połowie leży szukany gatunek. Każda runda odrzuca połowę listy, dlatego nawet w milionie wpisów wystarczy około 20 porównań, czyli O(log n).

Wbudowane sortowanie Pythona

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ć zadania z rozmów rekrutacyjnych
• 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 - w każdym przejściu największy z nieposortowanych elementów "wypływa" na koniec listy, jak bąbel na powierzchnię.

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# Przejście 1: ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python "wypłynął"
35# Przejście 2: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera "wypłynęła"
36# Przejście 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ź indeks 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: Gotowe

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 "środkowy" gatunek (pivot), 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 indeks 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  # Indeks 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

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()
8import random
9
10large_list = [random.random() for _ in range(10000)]
11sorted_list = sorted(large_list)  # Timsort - stabilny!
12
13# Duże dane, pamięć ograniczona, nie potrzebujesz stabilności
14# → Quick Sort (in-place)
15import random
16
17large_list = [random.random() for _ in range(10000)]
18quick_sort_inplace(large_list)  # Mało pamięci!
19
20# W praktyce: ZAWSZE używaj Python sort() lub sorted()
21# Są zoptymalizowane, stabilne i bardzo szybkie (Timsort)!
22animals.sort()  # Najlepszy wybór w 99% przypadków!

Sortowanie gatunków po różnych kryteriach

Klucz sortowania możesz zbudować z dowolnej informacji o gatunku. Poniżej ta sama lista słowników posortowana na trzy sposoby; zapis lambda s: s["name"] to krótka funkcja, która dla każdego gatunku podaje wartość do porównania (dokładniej omówimy ją w projekcie na końcu modułu):

1species_list = [
2    {"name": "Python regius", "size": 1.5, "dangerous": False},
3    {"name": "Panthera leo", "size": 2.5, "dangerous": True},
4    {"name": "Elephas maximus", "size": 3.5, "dangerous": False},
5    {"name": "Crocodylus niloticus", "size": 4.5, "dangerous": True},
6    {"name": "Gorilla gorilla", "size": 1.8, "dangerous": False}
7]
8
9# 1. Sortowanie po nazwie
10sorted_by_name = sorted(species_list, key=lambda s: s["name"])
11for s in sorted_by_name:
12    print(s["name"])
13# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius
14
15# 2. Sortowanie po rozmiarze (malejąco)
16sorted_by_size = sorted(species_list, key=lambda s: s["size"], reverse=True)
17for s in sorted_by_size:
18    print(f"{s['name']}: {s['size']}m")
19# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...
20
21# 3. Najpierw niebezpieczne, potem od największego
22sorted_by_danger_size = sorted(species_list, key=lambda s: (not s["dangerous"], -s["size"]))
23for s in sorted_by_danger_size:
24    danger = "niebezpieczny" if s["dangerous"] else "bezpieczny"
25    print(f"{s['name']}: {s['size']}m ({danger})")
26# Crocodylus niloticus: 4.5m (niebezpieczny)
27# Panthera leo: 2.5m (niebezpieczny)
28# Elephas maximus: 3.5m (bezpieczny)
29# ...

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

Poniższy przykład zamyka listę i funkcje w klasie - klasy poznasz w module 3, więc na razie czytaj go jak zestaw funkcji działających na jednej liście:

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

W edytorze czekają odległości do wodopoju i lista węży:

1. Posortuj listę distances rosnąco metodą sort() i ją wyświetl
2. Funkcją sorted() z reverse=True zbuduj z listy species nową listę malejącą, nie zmieniając oryginału

1# Sortowanie list
2# .sort() zmienia oryginalną listę, sorted() tworzy nową
3
4animal_weights = [450, 120, 5000, 30, 900, 1500]
5animal_names = ["gepard", "lew", "słoń", "zebra", "antylopa", "bawół"]
6
7# sort() - sortuje w miejscu (zmienia oryginalną listę)
8animal_weights.sort()
9print(f"Wagi rosnąco: {animal_weights}")
10
11animal_weights.sort(reverse=True)
12print(f"Wagi malejąco: {animal_weights}")
13
14# sorted() - zwraca NOWĄ posortowaną listę
15sorted_names = sorted(animal_names)
16print(f"\nNazwy alfabetycznie: {sorted_names}")
17print(f"Oryginalna lista: {animal_names}")  # Niezmieniona!
18
19# TODO: Stwórz listę odległości do wodopoju (w km)
20distances = [12.5, 3.2, 8.7, 1.1, 15.3, 6.4]
21
22# TODO: Posortuj distances rosnąco, używając .sort()
23
24
25# TODO: Wyświetl posortowaną listę
26print(f"Odległości rosnąco: {distances}")
27
28# TODO: Użyj sorted() z reverse=True, żeby uzyskać kolejność malejącą BEZ zmiany oryginalnej listy
29species = ["pyton", "kobra", "mamba", "anakonda", "boa"]
30sorted_desc = sorted(species)  # Dodaj reverse=True
31print(f"Gatunki malejąco: {sorted_desc}")
32

Podsumowanie

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

• Dlaczego sortowanie jest ważne
• Jak działa wyszukiwanie binarne i dlaczego wymaga posortowanej listy
• Wbudowane 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 słowników po różnych kryteriach 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 kompromis między czasem a pamięcią
• Potrafisz wybrać odpowiedni algorytm dla danej sytuacji

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

W następnej lekcji połączysz wszystko w projekcie Safari Species Tracker!