Kurs Python · Moduł 2: Struktury danych

Algorytmy sortowania - Klasyfikacja gatunków

15 min czytania ·
W tej lekcji16

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
# Przykład: Szukanie w posortowanej liście
species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]

# Binary search - O(log n) - ale wymaga sortowania!
import bisect
index = bisect.bisect_left(species, "Leo")  # Szybkie!

# vs nieposortowana lista - O(n)
unsorted_species = ["Python", "Leo", "Gorilla", ...]
index = 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.
def binary_search(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        mid = (left + right) // 2       # 1. środek zakresu
        if sorted_list[mid] == target:  # 2. porównanie
            return mid                  # 4. znaleziono - zwróć pozycję
        elif sorted_list[mid] < target:
            left = mid + 1              # 3. szukaj w prawej połowie
        else:
            right = mid - 1             # 3. szukaj w lewej połowie
    return -1                           # 4. nie znaleziono

species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
print(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. list.sort() - sortuje in-place (modyfikuje oryginalną listę)
animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
animals.sort()  # Modyfikuje animals
print(animals)  # ['Lew', 'Papuga', 'Słoń', 'Tygrys']

# 2. sorted() - zwraca nową posortowaną listę
animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
sorted_animals = sorted(animals)  # Nowa lista
print(animals)  # ['Tygrys', 'Słoń', 'Lew', 'Papuga'] - niezmienione
print(sorted_animals)  # ['Lew', 'Papuga', 'Słoń', 'Tygrys']

# 3. Sortowanie z kluczem
animals = ["Tygrys", "Słoń", "Lew", "Papuga"]
sorted_by_length = sorted(animals, key=len)
print(sorted_by_length)  # ['Lew', 'Słoń', 'Tygrys', 'Papuga']

# 4. Odwrotne sortowanie
animals.sort(reverse=True)
print(animals)  # ['Tygrys', 'Słoń', 'Papuga', 'Lew']

# 5. Sortowanie dict po wartościach
species_count = {"Python": 5, "Leo": 3, "Elephas": 8}
sorted_species = sorted(species_count.items(), key=lambda x: x[1], reverse=True)
print(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ę.

def bubble_sort(arr):
    """
    Sortowanie bąbelkowe - O(n²)

    Algorytm:
    1. Przejdź przez całą listę
    2. Porównaj każdą parę sąsiednich elementów
    3. Zamień je miejscami, jeśli są w złej kolejności
    4. Powtarzaj, aż nic się nie zmienia
    """
    n = len(arr)

    for i in range(n):
        # Po każdej iteracji największy element "wypłynie" na koniec
        swapped = False  # Optymalizacja - jeśli nic nie zmieniliśmy, lista jest posortowana

        for j in range(0, n - i - 1):  # Pomijamy ostatnie i elementów (już posortowane)
            if arr[j] > arr[j + 1]:
                # Zamiana miejscami
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break  # Lista już posortowana

    return arr

# Przykład
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = bubble_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Krok po kroku:
# Przejście 1: ["Leo", "Elephas", "Gorilla", "Panthera", "Python"]  # Python "wypłynął"
# Przejście 2: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Panthera "wypłynęła"
# 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.

def selection_sort(arr):
    """
    Sortowanie przez wybieranie - O(n²)

    Algorytm:
    1. Znajdź najmniejszy element w nieposortowanej części
    2. Zamień go z pierwszym elementem nieposortowanej części
    3. Przesuń granicę posortowanej części o 1
    4. Powtarzaj
    """
    n = len(arr)

    for i in range(n):
        # Znajdź indeks najmniejszego elementu w nieposortowanej części
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Zamień najmniejszy element z pierwszym nieposortowanym
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

# Przykład
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = selection_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Krok po kroku:
# i=0: ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]  # Znaleziono min: Elephas
# i=1: ["Elephas", "Gorilla", "Python", "Leo", "Panthera"]  # Znaleziono min: Gorilla
# i=2: ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]  # Znaleziono min: Leo
# i=3: ["Elephas", "Gorilla", "Leo", "Panthera", "Python"]  # Znaleziono min: Panthera
# 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.

def insertion_sort(arr):
    """
    Sortowanie przez wstawianie - O(n²)

    Algorytm:
    1. Zacznij od drugiego elementu
    2. Porównaj go z elementami z lewej strony
    3. Przesuń większe elementy w prawo
    4. Wstaw element na właściwe miejsce
    5. Powtarzaj dla każdego elementu
    """
    for i in range(1, len(arr)):
        key = arr[i]  # Element do wstawienia
        j = i - 1

        # Przesuń elementy większe niż key o jedną pozycję w prawo
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Wstaw key na właściwe miejsce
        arr[j + 1] = key

    return arr

# Przykład
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = insertion_sort(species.copy())
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Krok po kroku:
# i=1 (Leo):      ["Leo", "Python", "Elephas", "Gorilla", "Panthera"]
# i=2 (Elephas):  ["Elephas", "Leo", "Python", "Gorilla", "Panthera"]
# i=3 (Gorilla):  ["Elephas", "Gorilla", "Leo", "Python", "Panthera"]
# 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.

def merge_sort(arr):
    """
    Sortowanie przez scalanie - O(n log n)

    Algorytm (Divide and Conquer):
    1. Jeśli lista ma 1 element - już posortowana
    2. Podziel listę na dwie połowy
    3. Posortuj każdą połowę rekurencyjnie
    4. Scal dwie posortowane połówki
    """
    if len(arr) <= 1:
        return arr

    # Dziel
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Scalaj
    return merge(left, right)

def merge(left, right):
    """
    Scal dwie posortowane listy w jedną posortowaną listę
    """
    result = []
    i = j = 0

    # Porównuj elementy z obu list i dodawaj mniejszy
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Dodaj pozostałe elementy (jedna z list jest pusta)
    result.extend(left[i:])
    result.extend(right[j:])

    return result

# Przykład
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = merge_sort(species)
print(sorted_species)  # ['Elephas', 'Gorilla', 'Leo', 'Panthera', 'Python']

# Drzewo rekurencji:
# ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
#       /                                  \
# ["Python", "Leo"]                  ["Elephas", "Gorilla", "Panthera"]
#   /        \                           /                \
# ["Python"] ["Leo"]               ["Elephas"]    ["Gorilla", "Panthera"]
#                                                      /            \
#                                                ["Gorilla"]    ["Panthera"]
# Scalanie:
# ["Leo", "Python"]                 ["Elephas", "Gorilla", "Panthera"]
#                \                    /
#         ['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.

def quick_sort(arr):
    """
    Sortowanie szybkie - O(n log n) średnio, O(n²) najgorszy

    Algorytm:
    1. Jeśli lista ma ≤1 element - już posortowana
    2. Wybierz pivot (np. ostatni element)
    3. Podziel na: mniejsze od pivot, równe pivot, większe od pivot
    4. Posortuj rekurencyjnie mniejsze i większe
    5. Połącz: [posortowane mniejsze] + [pivot] + [posortowane większe]
    """
    if len(arr) <= 1:
        return arr

    # Wybierz pivot (np. ostatni element)
    pivot = arr[-1]

    # Podziel na 3 grupy
    smaller = [x for x in arr[:-1] if x < pivot]
    equal = [x for x in arr if x == pivot]
    larger = [x for x in arr[:-1] if x > pivot]

    # Rekurencyjnie posortuj i połącz
    return quick_sort(smaller) + equal + quick_sort(larger)

# Bardziej efektywna wersja (in-place):
def quick_sort_inplace(arr, low=0, high=None):
    """Quick sort in-place z partycjonowaniem Lomuto"""
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Partycjonuj i otrzymaj indeks pivota
        pivot_index = partition(arr, low, high)

        # Posortuj części przed i po pivocie
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

    return arr

def partition(arr, low, high):
    """Partycjonowanie Lomuto"""
    pivot = arr[high]  # Wybierz ostatni element jako pivot
    i = low - 1  # Indeks mniejszego elementu

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    # Umieść pivot na właściwym miejscu
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Przykład
species = ["Python", "Leo", "Elephas", "Gorilla", "Panthera"]
sorted_species = quick_sort(species)
print(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

AlgorytmNajlepszyŚredniNajgorszyPamięćStabilny
Bubble SortO(n)O(n²)O(n²)O(1)Tak
Selection SortO(n²)O(n²)O(n²)O(1)Nie
Insertion SortO(n)O(n²)O(n²)O(1)Tak
Merge SortO(n log n)O(n log n)O(n log n)O(n)Tak
Quick SortO(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?

# Małe dane (<50 elementów) lub prawie posortowane
# → Insertion Sort
small_list = ["Python", "Leo", "Elephas"]
insertion_sort(small_list)  # Szybkie dla małych danych!

# Duże dane, potrzebujesz stabilności
# → Merge Sort lub Python sort()
import random

large_list = [random.random() for _ in range(10000)]
sorted_list = sorted(large_list)  # Timsort - stabilny!

# Duże dane, pamięć ograniczona, nie potrzebujesz stabilności
# → Quick Sort (in-place)
import random

large_list = [random.random() for _ in range(10000)]
quick_sort_inplace(large_list)  # Mało pamięci!

# W praktyce: ZAWSZE używaj Python sort() lub sorted()
# Są zoptymalizowane, stabilne i bardzo szybkie (Timsort)!
animals.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):

species_list = [
    {"name": "Python regius", "size": 1.5, "dangerous": False},
    {"name": "Panthera leo", "size": 2.5, "dangerous": True},
    {"name": "Elephas maximus", "size": 3.5, "dangerous": False},
    {"name": "Crocodylus niloticus", "size": 4.5, "dangerous": True},
    {"name": "Gorilla gorilla", "size": 1.8, "dangerous": False}
]

# 1. Sortowanie po nazwie
sorted_by_name = sorted(species_list, key=lambda s: s["name"])
for s in sorted_by_name:
    print(s["name"])
# Crocodylus niloticus, Elephas maximus, Gorilla gorilla, Panthera leo, Python regius

# 2. Sortowanie po rozmiarze (malejąco)
sorted_by_size = sorted(species_list, key=lambda s: s["size"], reverse=True)
for s in sorted_by_size:
    print(f"{s['name']}: {s['size']}m")
# Crocodylus niloticus: 4.5m, Elephas maximus: 3.5m, Panthera leo: 2.5m, ...

# 3. Najpierw niebezpieczne, potem od największego
sorted_by_danger_size = sorted(species_list, key=lambda s: (not s["dangerous"], -s["size"]))
for s in sorted_by_danger_size:
    danger = "niebezpieczny" if s["dangerous"] else "bezpieczny"
    print(f"{s['name']}: {s['size']}m ({danger})")
# Crocodylus niloticus: 4.5m (niebezpieczny)
# Panthera leo: 2.5m (niebezpieczny)
# Elephas maximus: 3.5m (bezpieczny)
# ...

Counting Sort - dla specjalnych przypadków

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

def counting_sort(arr, max_value):
    """
    Counting sort - O(n + k) gdzie k = max_value

    Działa tylko dla liczb całkowitych z zakresu [0, max_value]
    """
    # Zlicz wystąpienia każdej liczby
    count = [0] * (max_value + 1)
    for num in arr:
        count[num] += 1

    # Zbuduj posortowaną listę
    sorted_arr = []
    for num, freq in enumerate(count):
        sorted_arr.extend([num] * freq)

    return sorted_arr

# Safari przykład: Sortowanie liczby odkryć (0-100)
daily_discoveries = [5, 3, 8, 3, 12, 5, 7, 3, 10, 5]
sorted_discoveries = counting_sort(daily_discoveries, max(daily_discoveries))
print(sorted_discoveries)  # [3, 3, 3, 5, 5, 5, 7, 8, 10, 12]

# 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:

class SpeciesCatalog:
    """System katalogowania gatunków z różnymi sortowaniami"""

    def __init__(self):
        self.species = []

    def add_species(self, name, size, habitat, dangerous):
        """Dodaj gatunek do katalogu"""
        self.species.append({
            "name": name,
            "size": size,
            "habitat": habitat,
            "dangerous": dangerous
        })

    def sort_by_name(self):
        """Sortuj alfabetycznie"""
        return sorted(self.species, key=lambda s: s["name"])

    def sort_by_size(self, descending=True):
        """Sortuj po rozmiarze"""
        return sorted(self.species, key=lambda s: s["size"], reverse=descending)

    def sort_by_danger_then_size(self):
        """Sortuj: niebezpieczne najpierw, potem po rozmiarze"""
        return sorted(self.species, key=lambda s: (not s["dangerous"], -s["size"]))

    def filter_and_sort(self, habitat=None, min_size=None, sort_by="name"):
        """Filtruj i sortuj"""
        filtered = self.species

        if habitat:
            filtered = [s for s in filtered if s["habitat"] == habitat]

        if min_size:
            filtered = [s for s in filtered if s["size"] >= min_size]

        if sort_by == "name":
            return sorted(filtered, key=lambda s: s["name"])
        elif sort_by == "size":
            return sorted(filtered, key=lambda s: s["size"], reverse=True)

        return filtered

# Użycie
catalog = SpeciesCatalog()
catalog.add_species("Python regius", 1.5, "jungle", False)
catalog.add_species("Panthera leo", 2.5, "savanna", True)
catalog.add_species("Elephas maximus", 3.5, "jungle", False)
catalog.add_species("Crocodylus niloticus", 4.5, "river", True)

# Duże gatunki z dżungli, posortowane po rozmiarze
jungle_large = catalog.filter_and_sort(habitat="jungle", min_size=2.0, sort_by="size")
for s in jungle_large:
    print(f"{s['name']}: {s['size']}m")
# 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
Kod do tej lekcji: main.py
# Sortowanie list
# .sort() zmienia oryginalną listę, sorted() tworzy nową

animal_weights = [450, 120, 5000, 30, 900, 1500]
animal_names = ["gepard", "lew", "słoń", "zebra", "antylopa", "bawół"]

# sort() - sortuje w miejscu (zmienia oryginalną listę)
animal_weights.sort()
print(f"Wagi rosnąco: {animal_weights}")

animal_weights.sort(reverse=True)
print(f"Wagi malejąco: {animal_weights}")

# sorted() - zwraca NOWĄ posortowaną listę
sorted_names = sorted(animal_names)
print(f"\nNazwy alfabetycznie: {sorted_names}")
print(f"Oryginalna lista: {animal_names}")  # Niezmieniona!

# TODO: Stwórz listę odległości do wodopoju (w km)
distances = [12.5, 3.2, 8.7, 1.1, 15.3, 6.4]

# TODO: Posortuj distances rosnąco, używając .sort()


# TODO: Wyświetl posortowaną listę
print(f"Odległości rosnąco: {distances}")

# TODO: Użyj sorted() z reverse=True, żeby uzyskać kolejność malejącą BEZ zmiany oryginalnej listy
species = ["pyton", "kobra", "mamba", "anakonda", "boa"]
sorted_desc = sorted(species)  # Dodaj reverse=True
print(f"Gatunki malejąco: {sorted_desc}")

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!

Hasła z dokumentacji w tej lekcji

Widzisz błąd w tej lekcji?

Sprawdź się

Odpowiedz na pytania z tej lekcji. Wybierz odpowiedź, a od razu zobaczysz, czy jest poprawna.

  1. 1. Jaka jest złożoność czasowa Bubble Sort w najgorszym przypadku?

  2. 2. Jaki warunek musi spełniać lista dla Binary Search?

  3. 3. Który algorytm sortowania jest najszybszy dla dużych danych?

Zadania praktyczne w grze

  • Klikanie w kolejności

    Kliknij elementy w prawidłowej kolejności:

  • Układanie w pionie

    Uporządkuj kroki Binary Search:

  1. PytanieSortowanie bąbelkowe
  2. PytanieWyszukiwanie binarne - warunek
  3. PytanieZłożoność algorytmów
  4. Kliknij w kolejnościBudowanie dict.items()
  5. Ułóż w kolejnościKroki wyszukiwania binarnego

Przydatne artykuły