Kurs Python · Moduł 2: Struktury danych
Algorytmy sortowania - Klasyfikacja gatunków
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 listWyszukiwanie 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:
- Znajdź środkowy element przeszukiwanego zakresu.
- Porównaj go z szukaną wartością.
- Jeśli to nie on, wybierz lewą albo prawą połowę - tę, w której szukana wartość może się jeszcze znajdować.
- 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")) # 2Lista 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ż posortowaneZł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: GotoweZł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
| 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?
# 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.5mZadanie praktyczne
W edytorze czekają odległości do wodopoju i lista węży:
- Posortuj listę
distancesrosnąco metodąsort()i ją wyświetl - Funkcją
sorted()zreverse=Truezbuduj z listyspeciesnową 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. Jaka jest złożoność czasowa Bubble Sort w najgorszym przypadku?
2. Jaki warunek musi spełniać lista dla Binary Search?
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: