Algorytmy — podstawy

1. Czym jest algorytm?

Algorytm to skończony, jednoznaczny ciąg kroków prowadzący do rozwiązania problemu. Każdy krok musi być precyzyjny i wykonywalny.

Skończony — musi się kiedyś zakończyć
Jednoznaczny — każdy krok ma jedno znaczenie
Poprawny — dla poprawnych danych daje poprawny wynik
Ogólny — działa dla całej klasy problemów, nie tylko jednego przypadku

Złożoność obliczeniowa Opisuje jak rośnie czas działania wraz z rozmiarem danych n. O(1) — stały, O(n) — liniowy, O(n²) — kwadratowy, O(log n) — logarytmiczny. Na egzaminie ważna jest intuicja — ile pętli, ile operacji.

Schemat blokowy — legenda

# Elementy schematu blokowego:
#
#  ┌──────────┐
#  │  START   │   — owal: początek i koniec
#  └──────────┘
#
#  ┌──────────┐
#  │  x = 5   │   — prostokąt: operacja/instrukcja
#  └──────────┘
#
#  ◇ x > 0 ◇      — romb: warunek (TAK/NIE)
#
#  ┌──────────┐
#  │ Wczytaj x│   — równoległobok: wejście/wyjście
#  └──────────┘
#
# Strzałki łączą elementy i pokazują przepływ.
# Na egzaminie możesz być poproszona o:
# - narysowanie schematu dla algorytmu
# - implementację algorytmu ze schematu
# - analizę co robi schemat

2. Wyszukiwanie liniowe (sekwencyjne)

Najprostszy algorytm wyszukiwania — sprawdzamy każdy element po kolei aż znajdziemy szukanego lub przejdziemy całą listę.

Złożoność: O(n) — w najgorszym przypadku sprawdzamy każdy element
Działa na: dowolnej liście — posortowanej i nieposortowanej
Najlepszy przypadek: O(1) — szukany element na pierwszym miejscu
Najgorszy przypadek: O(n) — element na końcu lub go nie ma

Schemat blokowy — wyszukiwanie liniowe START → wczytaj listę i szukaną → i = 0 → czy i < n? →NIE→ "nie znaleziono" → KONIEC
→TAK→ czy lista[i] == szukana? →TAK→ zwróć i → KONIEC
→NIE→ i = i + 1 → (wróć do sprawdzenia i < n)

Implementacja — wyszukiwanie liniowe

def wyszukiwanie_liniowe(lista, szukana):
    """Zwraca indeks szukanego elementu lub -1."""
    for i in range(len(lista)):
        if lista[i] == szukana:
            return i
    return -1

# Wersja z enumerate (czytelniejsza)
def wyszukiwanie_liniowe_v2(lista, szukana):
    for i, elem in enumerate(lista):
        if elem == szukana:
            return i
    return -1

# Test
liczby = [64, 34, 25, 12, 22, 11, 90]

wynik = wyszukiwanie_liniowe(liczby, 22)
print(f"22 → indeks: {wynik}")     # 4

wynik = wyszukiwanie_liniowe(liczby, 99)
print(f"99 → indeks: {wynik}")     # -1

# Wyszukiwanie wszystkich wystąpień
def znajdz_wszystkie(lista, szukana):
    return [i for i, x in enumerate(lista) if x == szukana]

dane = [3, 5, 2, 5, 8, 5, 1]
print(znajdz_wszystkie(dane, 5))   # [1, 3, 5]

3. Sortowanie bąbelkowe (Bubble Sort)

Algorytm wielokrotnie przechodzi przez listę, porównując sąsiednie elementy i zamieniając je jeśli są w złej kolejności. Większe elementy "wypływają" na koniec jak bąbelki.

Złożoność: O(n²) — dwie zagnieżdżone pętle
Stabilny — zachowuje kolejność równych elementów
W miejscu — nie potrzebuje dodatkowej pamięci
Po każdym przebiegu zewnętrznej pętli największy element trafia na właściwe miejsce
Optymalizacja: jeśli żadna zamiana w przebiegu — lista posortowana, można przerwać

Liczba przebiegów Dla listy n-elementowej potrzeba co najwyżej n-1 przebiegów zewnętrznej pętli. Po i-tym przebiegu ostatnie i elementów jest już na swoim miejscu.

Implementacja — sortowanie bąbelkowe

def bubble_sort(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]

# Wersja z optymalizacją (early exit)
def bubble_sort_opt(lista):
    n = len(lista)
    for i in range(n - 1):
        zamieniono = False
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                zamieniono = True
        if not zamieniono:
            break   # lista już posortowana!

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

# Śledzenie kroków
def bubble_sort_debug(lista):
    n = len(lista)
    krok = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                krok += 1
                print(f"Krok {krok}: {lista}")
    return krok

4. Sortowanie przez wybieranie (Selection Sort)

Algorytm dzieli listę na część posortowaną (lewa) i nieposortowaną (prawa). W każdym kroku znajduje minimum w części nieposortowanej i przenosi je na koniec części posortowanej.

Złożoność: O(n²) — zawsze, niezależnie od danych
Niestabilny — może zmieniać kolejność równych elementów
W miejscu — nie potrzebuje dodatkowej pamięci
Zawsze wykonuje dokładnie n-1 zamian — mniej zamian niż bubble sort
Dobry gdy koszt zamiany jest wysoki

Różnica vs bubble sort Bubble sort zamienia wiele razy w każdym przebiegu. Selection sort robi dokładnie jedną zamianę na przebieg (lub zero jeśli min jest już na miejscu). Mniej zamian, ale tyle samo porównań.

Implementacja — sortowanie przez wybieranie

def selection_sort(lista):
    n = len(lista)
    for i in range(n - 1):
        # Znajdź indeks minimum w podliście [i..n-1]
        min_idx = i
        for j in range(i + 1, n):
            if lista[j] < lista[min_idx]:
                min_idx = j
        # Zamień minimum z elementem na pozycji i
        if min_idx != i:
            lista[i], lista[min_idx] = lista[min_idx], lista[i]

# Test z krokami
def selection_sort_debug(lista):
    n = len(lista)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if lista[j] < lista[min_idx]:
                min_idx = j
        if min_idx != i:
            lista[i], lista[min_idx] = lista[min_idx], lista[i]
        print(f"i={i}: {lista} (min był na {min_idx})")

dane = [64, 25, 12, 22, 11]
selection_sort_debug(dane)
# i=0: [11, 25, 12, 22, 64]
# i=1: [11, 12, 25, 22, 64]
# i=2: [11, 12, 22, 25, 64]
# i=3: [11, 12, 22, 25, 64]

5. Porównanie algorytmów sortowania

Algorytm	Najlepszy	Średni	Najgorszy	Pamięć	Stabilny
Bubble Sort	O(n)*	O(n²)	O(n²)	O(1)	✓
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓
Python sort()	O(n)	O(n log n)	O(n log n)	O(n)	✓

* z optymalizacją early exit

Na egzaminie Musisz umieć napisać bubble sort i selection sort z pamięci. Znaj ich złożoność O(n²). Wbudowany sort() jest szybszy — używaj go w praktyce, ale na egzaminie często proszą o własną implementację.

Przykład — porównanie na tej samej liście

import time
import random

def zmierz(func, dane):
    kopia = dane[:]   # kopia żeby nie modyfikować oryginału
    start = time.time()
    func(kopia)
    return time.time() - start

# Generuj losową listę
n    = 1000
dane = [random.randint(1, 10000) for _ in range(n)]

t_bubble    = zmierz(bubble_sort, dane)
t_selection = zmierz(selection_sort, dane)

print(f"Bubble sort:    {t_bubble:.4f}s")
print(f"Selection sort: {t_selection:.4f}s")

# Dla porównania — wbudowany sort
kopia = dane[:]
start = time.time()
kopia.sort()
t_wbudowany = time.time() - start
print(f"Wbudowany sort: {t_wbudowany:.6f}s  (znacznie szybszy!)")

6. Znajdowanie minimum i maksimum — własna implementacja

Zadanie klasyczne na egzaminie — znajdź minimum lub maksimum bez użycia wbudowanych funkcji min() i max().

Inicjalizuj wynik pierwszym elementem listy
Iteruj od drugiego elementu
Aktualizuj wynik gdy znajdziesz lepszy element
Złożoność: O(n) — jeden przebieg przez listę
Można jednocześnie śledzić indeks elementu

Pułapka — inicjalizacja Nie inicjalizuj minimum wartością 0 ani 999999 — zainicjuj pierwszym elementem listy. Jeśli wszystkie elementy są większe od 0, sztuczne minimum 0 nigdy nie zostanie zaktualizowane.

Implementacja — min, max i ich indeksy

def znajdz_min(lista):
    if not lista:
        return None
    minimum = lista[0]
    for elem in lista[1:]:
        if elem < minimum:
            minimum = elem
    return minimum

def znajdz_min_z_indeksem(lista):
    if not lista:
        return None, -1
    min_val = lista[0]
    min_idx = 0
    for i in range(1, len(lista)):
        if lista[i] < min_val:
            min_val = lista[i]
            min_idx = i
    return min_val, min_idx

def znajdz_max(lista):
    if not lista:
        return None
    maksimum = lista[0]
    for elem in lista[1:]:
        if elem > maksimum:
            maksimum = elem
    return maksimum

# Test
dane = [64, 34, 25, 12, 22, 11, 90, 11]
print(f"Min: {znajdz_min(dane)}")         # 11
val, idx = znajdz_min_z_indeksem(dane)
print(f"Min: {val} na pozycji {idx}")    # 11 na pozycji 5
print(f"Max: {znajdz_max(dane)}")         # 90

Zadania przykładowe z omówieniem

Zadanie 1 Sortowanie bąbelkowe — krok po kroku łatwe

Posortuj listę [5, 3, 8, 1, 9, 2] algorytmem bubble sort. Wypisz stan listy po każdym pełnym przebiegu zewnętrznej pętli. Policz łączną liczbę wykonanych zamian.

Rozwiązanie

lista    = [5, 3, 8, 1, 9, 2]
n        = len(lista)
zamiany  = 0

print(f"Start:      {lista}")

for i in range(n - 1):
    for j in range(n - 1 - i):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j+1] = lista[j+1], lista[j]
            zamiany += 1
    print(f"Przebieg {i+1}: {lista}")

Omówienie krok po kroku

Zewnętrzna pętla — przebiegi
range(n-1) — dla 6 elementów potrzeba 5 przebiegów. Zmienna i liczy przebiegi od 0.
Wewnętrzna pętla — porównania
range(n-1-i) — z każdym przebiegiem porównujemy o jeden element mniej, bo ostatnie i elementów jest już posortowanych.
Zamiana bez zmiennej pomocniczej
lista[j], lista[j+1] = lista[j+1], lista[j] — Python pakuje prawą stronę w krotkę i rozpakowuje w lewo. Elegancki swap.
Wypisanie po każdym przebiegu
print jest poza wewnętrzną pętlą (ale w zewnętrznej) — wypisuje stan po każdym pełnym przebiegu.

Zadanie 2 Wyszukiwanie liniowe z licznikiem porównań łatwe

Napisz funkcję wyszukiwania liniowego która zwraca krotkę: (indeks lub -1, liczba porównań). Przetestuj dla kilku różnych szukanych wartości i sprawdź ile porównań trzeba wykonać.

Rozwiązanie

def wyszuk_liniowe(lista, szukana):
    porownania = 0
    for i, elem in enumerate(lista):
        porownania += 1
        if elem == szukana:
            return i, porownania
    return -1, porownania

dane = [11, 22, 33, 44, 55, 66, 77, 88, 99]

testy = [11, 55, 99, 42]
for szukana in testy:
    idx, ile = wyszuk_liniowe(dane, szukana)
    if idx >= 0:
        print(f"{szukana}: indeks {idx}, "
              f"porównań: {ile}")
    else:
        print(f"{szukana}: nie znaleziono, "
              f"porównań: {ile}")

Omówienie krok po kroku

Licznik przed porównaniem
porownania += 1 przed if — liczymy każde porównanie, nie tylko udane. Element na pozycji 0 wymaga 1 porównania, na pozycji n-1 wymaga n porównań.
Zwracanie krotki
return i, porownania — dwie wartości w krotce. Rozpakowywanie: idx, ile = wyszuk_liniowe(...).
Obserwacja wyników
Element 11 (pierwszy) — 1 porównanie. Element 99 (ostatni) — 9 porównań. Element 42 (brak) — 9 porównań (cała lista). To pokazuje O(n) w praktyce.

Zadanie 3 Sortowanie przez wybieranie — malejąco średnie

Zmodyfikuj selection sort żeby sortował malejąco (od największego do najmniejszego). Posortuj listę imion alfabetycznie i odwrotnie — zaadaptuj algorytm do tekstów.

Rozwiązanie

def selection_sort_malejaco(lista):
    n = len(lista)
    for i in range(n - 1):
        max_idx = i      # szukamy MAKSIMUM
        for j in range(i + 1, n):
            if lista[j] > lista[max_idx]:
                max_idx = j
        if max_idx != i:
            lista[i], lista[max_idx] = lista[max_idx], lista[i]

# Test — liczby malejąco
liczby = [64, 25, 12, 22, 11, 90]
selection_sort_malejaco(liczby)
print("Malejąco:", liczby)
# [90, 64, 25, 22, 12, 11]

# Imiona — rosnąco (porównanie stringów)
imiona = ["Zofia", "Kasia", "Marek", "Ala", "Piotr"]
n = len(imiona)
for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
        if imiona[j] < imiona[min_idx]:   # < dla stringów
            min_idx = j
    if min_idx != i:
        imiona[i], imiona[min_idx] = imiona[min_idx], imiona[i]
print("Alfa:", imiona)
# ['Ala', 'Kasia', 'Marek', 'Piotr', 'Zofia']

Omówienie krok po kroku

Zmiana minimum na maksimum
Jedyna różnica to szukanie max_idx zamiast min_idx i warunek > zamiast <. Logika algorytmu identyczna.
Porównanie stringów
Python porównuje stringi leksykograficznie — znak po znaku według kodu Unicode. "Ala" < "Kasia" bo 'A' < 'K'. Algorytm działa tak samo jak dla liczb.
Jeden algorytm, wiele zastosowań
Selection sort (i inne) działa dla dowolnego typu danych który można porównywać operatorami < i >. To pokazuje ogólność algorytmów.

Zadania do samodzielnego rozwiązania

Implementuj algorytmy samodzielnie — nie używaj wbudowanych sort(), min(), max() tam gdzie zadanie tego nie zezwala. To właśnie sprawdza egzamin.

1★☆☆

Drugi największy

Znajdź drugi największy element listy bez sortowania i bez max(). Obsłuż przypadek gdy wszystkie elementy są równe.

Wskazówka: śledź dwie zmienne: maks1 i maks2

2★☆☆

Liczenie zamian

Uruchom bubble sort i selection sort na tej samej liście 10 elementów. Porównaj ile zamian wykonał każdy algorytm.

Wskazówka: dodaj licznik zamian do obu funkcji, zwróć go

3★★☆

Sortowanie par

Masz listę par (imię, wynik). Posortuj ją algorytmem selection sort malejąco według wyniku. Przy równych wynikach sortuj imiona alfabetycznie.

Wskazówka: porównuj para[1], przy równości porównuj para[0]

4★★☆

Wyszukiwanie zakresu

Napisz funkcję która zwraca wszystkie elementy listy należące do zakresu [min_val, max_val]. Nie używaj list comprehension — użyj pętli for.

Wskazówka: if min_val <= elem <= max_val

5★★☆

Czy lista posortowana?

Napisz funkcję czy_posortowana(lista) sprawdzającą czy lista jest posortowana rosnąco — bez jej sortowania. Powinna działać w O(n).

Wskazówka: sprawdź czy każdy element jest ≤ następnemu

6★★★

Sortowanie przez zliczanie

Zaimplementuj Counting Sort dla listy liczb całkowitych z zakresu 0–100. Zlicz wystąpienia każdej wartości, a potem odtwórz posortowaną listę. Złożoność O(n+k).

Wskazówka: lista liczników [0]*101, potem odtwarzaj przez pętlę po licznikach