Algorytm to precyzyjny zestaw kroków prowadzących do rozwiązania problemu.

Dlaczego algorytmy?

• Efektywność – szybsze przetwarzanie danych
• Optymalizacja – mniej zasobów (pamięć, czas)
• Zrozumienie podstaw informatyki
• Rozmowy kwalifikacyjne

W tej lekcji:

• Algorytmy sortowania
• Algorytmy przeszukiwania
• Złożoność obliczeniowa (Big O)

Złożoność obliczeniowa (Big O Notation)

Złożoność obliczeniowa mierzy jak szybko rośnie czas wykonania algorytmu wraz ze wzrostem rozmiaru danych.

Notacja Big O

O(n) – „Big O of n” – opisuje najgorszy przypadek.

Najczęstsze złożoności (od najlepszej do najgorszej):

Wizualizacja wzrostu

n = 10:
O(1)      = 1
O(log n)  = 3
O(n)      = 10
O(n log n)= 30
O(n²)     = 100
O(2^n)    = 1024

n = 1000:
O(1)      = 1
O(log n)  = 10
O(n)      = 1000
O(n log n)= 10000
O(n²)     = 1000000
O(2^n)    = ???  (za dużo!)

Przykłady złożoności

# O(1) - Stała
def get_first(lista):
    return lista[0]  # Zawsze 1 operacja

# O(n) - Liniowa
def contains(lista, element):
    for item in lista:  # n operacji
        if item == element:
            return True
    return False

# O(n²) - Kwadratowa
def print_pairs(lista):
    for i in lista:       # n razy
        for j in lista:   # n razy
            print(i, j)   # n * n = n²

Algorytmy sortowania

Sortowanie to uporządkowanie elementów według określonego kryterium.

1. 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ż lista będzie posortowana.

Złożoność:

• Czasowa: O(n²) – najgorszy i średni przypadek
• Czasowa: O(n) – najlepszy przypadek (lista już posortowana)
• Pamięciowa: O(1) – sortowanie in-place

Kiedy używać:

• Małe zbiory danych
• Dane prawie posortowane
• Cel edukacyjny

def bubble_sort(lista):
    """
    Sortowanie bąbelkowe.
    Porównuje sąsiednie elementy i zamienia je miejscami.
    """
    n = len(lista)
    
    # Zewnętrzna pętla - liczba przejść
    for i in range(n):
        # Flaga - czy było zamiana
        zamiana = False
        
        # Wewnętrzna pętla - porównania
        for j in range(0, n - i - 1):
            # Jeśli element jest większy od następnego
            if lista[j] > lista[j + 1]:
                # Zamień miejscami
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                zamiana = True
        
        # Jeśli nie było zamiany, lista jest posortowana
        if not zamiana:
            break
    
    return lista

# Test
dane = [64, 34, 25, 12, 22, 11, 90]
print("Przed:", dane)
bubble_sort(dane)
print("Po:", dane)
# Po: [11, 12, 22, 25, 34, 64, 90]

Wizualizacja (pierwsze przejście):

[64, 34, 25, 12, 22, 11, 90]
 64>34 → zamień
[34, 64, 25, 12, 22, 11, 90]
    64>25 → zamień
[34, 25, 64, 12, 22, 11, 90]
       64>12 → zamień
[34, 25, 12, 64, 22, 11, 90]
          64>22 → zamień
[34, 25, 12, 22, 64, 11, 90]
             64>11 → zamień
[34, 25, 12, 22, 11, 64, 90]
                64<90 → OK

2. Selection Sort (Sortowanie przez wybieranie)

Idea: Znajdź najmniejszy element i umieść go na początku. Powtarzaj dla pozostałej części.

Złożoność:

• Czasowa: O(n²) – zawsze
• Pamięciowa: O(1)

def selection_sort(lista):
    """
    Sortowanie przez wybieranie.
    Znajduje minimum i umieszcza na początku.
    """
    n = len(lista)
    
    # Przejdź przez wszystkie elementy
    for i in range(n):
        # Znajdź indeks najmniejszego elementu
        min_idx = i
        for j in range(i + 1, n):
            if lista[j] < lista[min_idx]:
                min_idx = j
        
        # Zamień znaleziony minimum z pierwszym elementem
        lista[i], lista[min_idx] = lista[min_idx], lista[i]
    
    return lista

# Test
dane = [64, 25, 12, 22, 11]
print("Przed:", dane)
selection_sort(dane)
print("Po:", dane)
# Po: [11, 12, 22, 25, 64]

Wizualizacja:

[64, 25, 12, 22, 11]
 ^               ^  min=11, zamień
[11, 25, 12, 22, 64]
     ^   ^          min=12, zamień
[11, 12, 25, 22, 64]
         ^   ^      min=22, zamień
[11, 12, 22, 25, 64]
             ^  ^   min=25, już OK
[11, 12, 22, 25, 64] ✓

3. Insertion Sort (Sortowanie przez wstawianie)

Idea: Bierz kolejne elementy i wstawiaj je we właściwe miejsce w już posortowanej części.

Złożoność:

• Czasowa: O(n²) – najgorszy przypadek
• Czasowa: O(n) – najlepszy przypadek (lista posortowana)
• Pamięciowa: O(1)

Kiedy używać:

• Małe zbiory danych
• Dane prawie posortowane
• Sortowanie online (elementy przychodzą po kolei)

def insertion_sort(lista):
    """
    Sortowanie przez wstawianie.
    Jak sortowanie kart w ręce.
    """
    n = len(lista)
    
    # Zacznij od drugiego elementu
    for i in range(1, n):
        # Element do wstawienia
        key = lista[i]
        j = i - 1
        
        # Przesuń elementy większe od key o jedno miejsce w prawo
        while j >= 0 and lista[j] > key:
            lista[j + 1] = lista[j]
            j -= 1
        
        # Wstaw key na właściwe miejsce
        lista[j + 1] = key
    
    return lista

# Test
dane = [12, 11, 13, 5, 6]
print("Przed:", dane)
insertion_sort(dane)
print("Po:", dane)
# Po: [5, 6, 11, 12, 13]

Analogia: Jak sortowanie kart w ręce – bierzesz kolejną kartę i wstawiasz ją we właściwe miejsce.

4. Merge Sort (Sortowanie przez scalanie)

Idea: Dziel listę na połowy, sortuj rekurencyjnie, następnie scalaj posortowane połowy.

Złożoność:

• Czasowa: O(n log n) – zawsze!
• Pamięciowa: O(n) – wymaga dodatkowej pamięci

Kiedy używać:

• Duże zbiory danych
• Stabilne sortowanie (zachowuje kolejność równych elementów)
• Gwarantowana wydajność O(n log n)

def merge_sort(lista):
    """
    Sortowanie przez scalanie (rekurencyjne).
    Dziel i zwyciężaj.
    """
    # Warunek bazowy - lista o długości 1 jest posortowana
    if len(lista) <= 1:
        return lista
    
    # Podziel na dwie połowy
    srodek = len(lista) // 2
    lewa = lista[:srodek]
    prawa = lista[srodek:]
    
    # Rekurencyjnie posortuj połowy
    lewa = merge_sort(lewa)
    prawa = merge_sort(prawa)
    
    # Scal posortowane połowy
    return merge(lewa, prawa)

def merge(lewa, prawa):
    """Scala dwie posortowane listy."""
    wynik = []
    i = j = 0
    
    # Porównuj elementy z obu list
    while i < len(lewa) and j < len(prawa):
        if lewa[i] <= prawa[j]:
            wynik.append(lewa[i])
            i += 1
        else:
            wynik.append(prawa[j])
            j += 1
    
    # Dodaj pozostałe elementy
    wynik.extend(lewa[i:])
    wynik.extend(prawa[j:])
    
    return wynik

# Test
dane = [38, 27, 43, 3, 9, 82, 10]
print("Przed:", dane)
posortowane = merge_sort(dane)
print("Po:", posortowane)
# Po: [3, 9, 10, 27, 38, 43, 82]

Wizualizacja:

[38, 27, 43, 3, 9, 82, 10]
       ↓ dziel ↓
[38, 27, 43]  [3, 9, 82, 10]
  ↓ dziel ↓    ↓ dziel ↓
[38] [27, 43]  [3, 9] [82, 10]
       ↓          ↓       ↓
    [27, 43]    [3, 9]  [10, 82]
        ↓ scal ↓          ↓
    [27, 38, 43]    [3, 9, 10, 82]
           ↓ scal ↓
    [3, 9, 10, 27, 38, 43, 82]

5. Quick Sort (Sortowanie szybkie)

Idea: Wybierz element (pivot), podziel na mniejsze i większe, sortuj rekurencyjnie.

Złożoność:

• Czasowa: O(n log n) – średni przypadek
• Czasowa: O(n²) – najgorszy (rzadko)
• Pamięciowa: O(log n) – rekursja

Kiedy używać:

• Duże zbiory danych
• Najszybszy w praktyce
• Sortowanie in-place

def quick_sort(lista):
    """
    Sortowanie szybkie.
    Wybiera pivot i dzieli na mniejsze/większe.
    """
    # Warunek bazowy
    if len(lista) <= 1:
        return lista
    
    # Wybierz pivot (środkowy element)
    pivot = lista[len(lista) // 2]
    
    # Podziel na trzy grupy
    mniejsze = [x for x in lista if x < pivot]
    rowne = [x for x in lista if x == pivot]
    wieksze = [x for x in lista if x > pivot]
    
    # Rekurencyjnie posortuj i połącz
    return quick_sort(mniejsze) + rowne + quick_sort(wieksze)

# Test
dane = [10, 7, 8, 9, 1, 5]
print("Przed:", dane)
posortowane = quick_sort(dane)
print("Po:", posortowane)
# Po: [1, 5, 7, 8, 9, 10]

Wizualizacja:

[10, 7, 8, 9, 1, 5]  pivot=8
      ↓
mniejsze: [7, 1, 5]
rowne: [8]
wieksze: [10, 9]
      ↓ sortuj rekurencyjnie
[1, 5, 7] + [8] + [9, 10]
      ↓
[1, 5, 7, 8, 9, 10]

Porównanie algorytmów sortowania

Stabilny = zachowuje względną kolejność równych elementów.

Algorytmy przeszukiwania

1. Przeszukiwanie liniowe (Linear Search)

Idea: Sprawdź każdy element po kolei.

Złożoność:

• Czasowa: O(n)
• Pamięciowa: O(1)

Kiedy używać:

• Mała lista
• Lista nieposortowana
• Jednorazowe wyszukiwanie

def linear_search(lista, szukany):
    """
    Przeszukiwanie liniowe.
    Sprawdza każdy element po kolei.
    """
    for i in range(len(lista)):
        if lista[i] == szukany:
            return i  # Zwróć indeks
    return -1  # Nie znaleziono

# Test
dane = [10, 23, 45, 70, 11, 15]
wynik = linear_search(dane, 70)
print(f"Element 70 znajduje się na indeksie: {wynik}")  # 3

wynik = linear_search(dane, 100)
print(f"Element 100 znajduje się na indeksie: {wynik}")  # -1

2. Przeszukiwanie binarne (Binary Search)

Idea: W posortowanej liście sprawdź środek. Jeśli szukany jest mniejszy, szukaj w lewej połowie, jeśli większy – w prawej.

Złożoność:

• Czasowa: O(log n)
• Pamięciowa: O(1) – iteracyjna, O(log n) – rekurencyjna

Wymaganie: Lista MUSI być posortowana!

Kiedy używać:

• Duża, posortowana lista
• Wielokrotne wyszukiwania

def binary_search(lista, szukany):
    """
    Przeszukiwanie binarne (iteracyjne).
    Wymaga posortowanej listy!
    """
    lewy = 0
    prawy = len(lista) - 1
    
    while lewy <= prawy:
        # Znajdź środek
        srodek = (lewy + prawy) // 2
        
        # Sprawdź środkowy element
        if lista[srodek] == szukany:
            return srodek
        elif lista[srodek] < szukany:
            # Szukaj w prawej połowie
            lewy = srodek + 1
        else:
            # Szukaj w lewej połowie
            prawy = srodek - 1
    
    return -1  # Nie znaleziono

# Test
dane = [11, 15, 23, 45, 70]  # MUSI BYĆ POSORTOWANA!
wynik = binary_search(dane, 45)
print(f"Element 45 znajduje się na indeksie: {wynik}")  # 3

Wizualizacja:

Szukamy: 45
[11, 15, 23, 45, 70]
 L       M       P    środek=23, 45>23 → szukaj w prawo

         [45, 70]
          L   P       środek=45, znaleziono! ✓

Przeszukiwanie binarne – rekurencyjne

def binary_search_recursive(lista, szukany, lewy=0, prawy=None):
    """Przeszukiwanie binarne (rekurencyjne)."""
    if prawy is None:
        prawy = len(lista) - 1
    
    # Warunek bazowy
    if lewy > prawy:
        return -1
    
    # Znajdź środek
    srodek = (lewy + prawy) // 2
    
    if lista[srodek] == szukany:
        return srodek
    elif lista[srodek] < szukany:
        return binary_search_recursive(lista, szukany, srodek + 1, prawy)
    else:
        return binary_search_recursive(lista, szukany, lewy, srodek - 1)

# Test
dane = [11, 15, 23, 45, 70]
wynik = binary_search_recursive(dane, 70)
print(f"Element 70 znajduje się na indeksie: {wynik}")  # 4

Porównanie przeszukiwania

Przykład: Dla n=1,000,000

• Linear: max 1,000,000 porównań
• Binary: max ~20 porównań!

Praktyczne przykłady

Przykład 1: Benchmark sortowania

import time
import random

def benchmark_sort(funkcja_sort, dane, nazwa):
    """Mierzy czas sortowania."""
    kopia = dane.copy()
    start = time.time()
    funkcja_sort(kopia)
    koniec = time.time()
    print(f"{nazwa}: {koniec - start:.4f}s")

# Wygeneruj dane
dane = [random.randint(1, 1000) for _ in range(5000)]

print("Benchmark sortowania (5000 elementów):")
benchmark_sort(bubble_sort, dane, "Bubble Sort")
benchmark_sort(selection_sort, dane, "Selection Sort")
benchmark_sort(insertion_sort, dane, "Insertion Sort")
benchmark_sort(merge_sort, dane, "Merge Sort")
benchmark_sort(quick_sort, dane, "Quick Sort")
benchmark_sort(sorted, dane, "Python sorted()")

Przykład 2: Wyszukiwanie w bazie danych

class BazaDanych:
    def __init__(self):
        self.dane = []
    
    def dodaj(self, rekord):
        self.dane.append(rekord)
        # Sortuj po dodaniu (dla binary search)
        self.dane.sort(key=lambda x: x['id'])
    
    def znajdz_linear(self, id):
        """Wyszukiwanie liniowe."""
        for rekord in self.dane:
            if rekord['id'] == id:
                return rekord
        return None
    
    def znajdz_binary(self, id):
        """Wyszukiwanie binarne."""
        lewy, prawy = 0, len(self.dane) - 1
        
        while lewy <= prawy:
            srodek = (lewy + prawy) // 2
            if self.dane[srodek]['id'] == id:
                return self.dane[srodek]
            elif self.dane[srodek]['id'] < id:
                lewy = srodek + 1
            else:
                prawy = srodek - 1
        
        return None

# Test
db = BazaDanych()
db.dodaj({'id': 1, 'imie': 'Jan'})
db.dodaj({'id': 5, 'imie': 'Anna'})
db.dodaj({'id': 3, 'imie': 'Piotr'})

print(db.znajdz_binary(5))  # {'id': 5, 'imie': 'Anna'}

Wbudowane funkcje Pythona

Python ma wbudowane, bardzo zoptymalizowane funkcje sortowania.

# sorted() - zwraca nową posortowaną listę
dane = [3, 1, 4, 1, 5, 9, 2, 6]
posortowane = sorted(dane)
print(posortowane)  # [1, 1, 2, 3, 4, 5, 6, 9]

# sort() - sortuje in-place
dane = [3, 1, 4, 1, 5, 9, 2, 6]
dane.sort()
print(dane)  # [1, 1, 2, 3, 4, 5, 6, 9]

# Malejąco
dane.sort(reverse=True)
print(dane)  # [9, 6, 5, 4, 3, 2, 1, 1]

# Sortowanie z kluczem
osoby = [{'imie': 'Jan', 'wiek': 25}, 
         {'imie': 'Anna', 'wiek': 30}]
osoby.sort(key=lambda x: x['wiek'])
print(osoby)

Algorytm: Python używa Timsort (hybrydowy Merge Sort + Insertion Sort) – O(n log n).

Podsumowanie

Sortowanie:

• Bubble Sort – O(n²), prosty, edukacyjny
• Selection Sort – O(n²), prosty
• Insertion Sort – O(n²), dobry dla małych/prawie posortowanych
• Merge Sort – O(n log n), stabilny, wymaga pamięci
• Quick Sort – O(n log n) średnio, najszybszy praktycznie
• Python sort() – Timsort, O(n log n), używaj tego!

Przeszukiwanie:

• Linear Search – O(n), dla nieposortowanych
• Binary Search – O(log n), dla posortowanych

Złożoność:

• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)

Zasada: Dla małych danych (< 1000) różnice są niewielkie. Dla dużych – algorytm ma ogromne znaczenie!