3.4 Søke- og sorteringsalgoritmer

Søke- og sorteringsalgoritmar

Tenk deg at du har ein telefonkatalog med 10 000 namn. Viss du skal finne nummeret til «Olsen», kan du starte frå byrjinga og sjekke kvart namn. Men det er jo ikkje slik du faktisk brukar ein telefonkatalog. Du slår opp omtrent midt i boka, ser at du er på «M», og veit at «O» er litt lenger bak. Deretter halverer du igjen og igjen til du finn rett side. Denne intuitive metoden er faktisk ein av dei viktigaste algoritmane i informatikk: binærsøk.

Søking og sortering er to av dei mest grunnleggjande operasjonane i informatikk. Praktisk talt alle program som arbeider med data, må søkje i data og sortere data. E-postprogrammet ditt sorterer meldingar etter dato. Nettbutikken sorterer produkt etter pris. Søkjemotorar søkjer gjennom milliardar av nettsider for å finne det du leitar etter.

I dette kapittelet skal du lære å implementere dei mest kjende søke- og sorteringsalgoritmane i Python, forstå korleis dei fungerer, og samanlikne dei med omsyn til effektivitet.

Lineært søk

Lineært søk er som å leite etter ei bestemt bok i ei usortert bokhylle. Du byrjar med den første boka, sjekkar om det er rett bok, og viss ikkje, går du vidare til neste. Du held fram til du finn boka eller har sjekka alle.

Algoritme:
1. Start frå det første elementet i lista
2. Samanlikn elementet med det du søkjer etter
3. Viss det er likt, returner posisjonen
4. Viss ikkje, gå til neste element
5. Viss du har sjekka alle element utan å finne, returner «ikkje funne»

def lineaert_sok(liste, sokeord):
    """Søker etter sokeord i listen. Returnerer indeksen eller -1."""
    for i in range(len(liste)):
        if liste[i] == sokeord:
            return i  # Funnet på posisjon i
    return -1  # Ikke funnet

# Eksempel
tall = [4, 7, 2, 9, 1, 5, 8, 3, 6]

resultat = lineaert_sok(tall, 5)
if resultat != -1:
    print(f"Fant 5 på posisjon {resultat}")
else:
    print("Fant ikke 5")

resultat = lineaert_sok(tall, 10)
if resultat != -1:
    print(f"Fant 10 på posisjon {resultat}")
else:
    print("Fant ikke 10")

Kjøring:

Fant 5 på posisjon 5
Fant ikke 10

Analyse: For ei liste med n element må lineært søk i gjennomsnitt sjekke n/2 element, og i verste fall alle n. Vi seier at lineært søk har tidskompleksitet O(n), der n er talet på element. For ei liste med 1 000 000 element kan det ta opptil 1 000 000 samanlikningar.

Binærsøk

Binærsøk er som å slå opp i ein telefonkatalog. Fordi namna er sortert alfabetisk, kan du halvere søkjeområdet i kvart steg.

Algoritme:
1. Set lav til 0 og hoy til siste indeks
2. Finn midt = (lav + hoy) // 2
3. Viss elementet på midt er det du søkjer, returner midt
4. Viss elementet på midt er for stort, set hoy = midt - 1
5. Viss elementet på midt er for lite, set lav = midt + 1
6. Gjenta frå steg 2 så lenge lav <= hoy
7. Viss lav > hoy, er elementet ikkje i lista

def binaersok(sortert_liste, sokeord):
    """Binærsøk i en sortert liste. Returnerer indeksen eller -1."""
    lav = 0
    hoy = len(sortert_liste) - 1

    while lav <= hoy:
        midt = (lav + hoy) // 2

        if sortert_liste[midt] == sokeord:
            return midt  # Funnet!
        elif sortert_liste[midt] < sokeord:
            lav = midt + 1  # Søk i høyre halvdel
        else:
            hoy = midt - 1  # Søk i venstre halvdel

    return -1  # Ikke funnet

# Eksempel
sortert = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print(binaersok(sortert, 7))   # 3 (posisjon 3)
print(binaersok(sortert, 12))  # -1 (ikke funnet)

Trinnvis gjennomgang for å finne 7 i [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]:

Boblesortering (Bubble Sort)

Boblesortering er den enklaste sorteringsalgoritmen å forstå. Ideen er å gjentekne gonger gå gjennom lista og samanlikne naboelement. Viss to naboelement er i feil rekkefølgje, byter vi dei. Vi gjentek dette til lista er sortert.

Namnet «boblesortering» kjem av at dei største elementa gradvis «boblar opp» til rett posisjon, akkurat som luftboblar stig til overflata i eit glas vatn.

def boblesortering(liste):
    """Sorterer en liste med boblesortering."""
    n = len(liste)

    for i in range(n - 1):
        byttet = False

        for j in range(n - 1 - i):
            if liste[j] > liste[j + 1]:
                # Bytt naboelementer
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                byttet = True

        # Optimalisering: hvis ingen bytter ble gjort, er listen sortert
        if not byttet:
            break

    return liste

# Eksempel
tall = [64, 34, 25, 12, 22, 11, 90]
print(f"Usortert: {tall}")
boblesortering(tall)
print(f"Sortert:  {tall}")

Kjøring:

Usortert: [64, 34, 25, 12, 22, 11, 90]
Sortert:  [11, 12, 22, 25, 34, 64, 90]

Trinnvis eksempel med [5, 3, 1, 4, 2]:

Gjennomgang 1: [3, 1, 4, 2, 5] (5 boblar opp til slutten)
Gjennomgang 2: [1, 3, 2, 4, 5] (4 på plass)
Gjennomgang 3: [1, 2, 3, 4, 5] (3 på plass)
Gjennomgang 4: [1, 2, 3, 4, 5] (ingen byte, ferdig!)

Boblesortering er enkel og intuitiv, men han er treg for store datasett fordi han i verste fall treng omtrent n² samanlikningar.

Innsetjingssortering (Insertion Sort)

Innsetjingssortering fungerer som du sorterer spelkort på handa. Du tek eitt kort om gongen frå bunken og set det inn på rett plass blant dei korta du allereie held sorterte.

Algoritme:
1. Start med det andre elementet (det første er «sortert» åleine)
2. Ta elementet og samanlikn det med elementa til venstre
3. Flytt elementa som er større eitt steg til høgre
4. Set inn elementet på rett plass
5. Gjenta for alle attståande element

def innsettingssortering(liste):
    """Sorterer en liste med innsettingssortering."""
    for i in range(1, len(liste)):
        nokkel = liste[i]  # Elementet vi skal sette inn
        j = i - 1

        # Flytt elementer som er større enn nøkkelen
        while j >= 0 and liste[j] > nokkel:
            liste[j + 1] = liste[j]
            j -= 1

        # Sett inn nøkkelen på riktig plass
        liste[j + 1] = nokkel

    return liste

# Eksempel
tall = [5, 3, 1, 4, 2]
print(f"Usortert: {tall}")
innsettingssortering(tall)
print(f"Sortert:  {tall}")

Trinnvis for [5, 3, 1, 4, 2]:

Utvalssortering (Selection Sort)

Utvalssortering er ein annan enkel sorteringsalgoritme. Ideen er: finn det minste elementet og plasser det først. Finn deretter det nest minste og plasser det på posisjon 2, og så vidare.

def utvalgssortering(liste):
    """Sorterer en liste med utvalgssortering."""
    n = len(liste)

    for i in range(n - 1):
        # Finn indeksen til det minste elementet i resten av listen
        min_indeks = i
        for j in range(i + 1, n):
            if liste[j] < liste[min_indeks]:
                min_indeks = j

        # Bytt det minste elementet med elementet på posisjon i
        liste[i], liste[min_indeks] = liste[min_indeks], liste[i]

    return liste

# Eksempel
tall = [29, 10, 14, 37, 13]
print(f"Usortert: {tall}")
utvalgssortering(tall)
print(f"Sortert:  {tall}")

Trinnvis for [29, 10, 14, 37, 13]:

Samanlikning av søke- og sorteringsalgoritmar

Søkjealgoritmar:

Alle tre sorteringsalgoritmane har tidskompleksitet O(n²) i verste fall, noko som betyr at dei blir svært trege for store datamengder. I praksis brukar Python den innebygde funksjonen sorted() eller metoden .sort(), som brukar Timsort-algoritmen med tidskompleksitet O(n log n), noko som er vesentleg raskare.

# Pythons innebygde sortering (Timsort) – bruk denne i praksis!
tall = [64, 34, 25, 12, 22, 11, 90]
sortert = sorted(tall)        # Lager ny sortert liste
tall.sort()                    # Sorterer listen direkte

Likevel er det verdifullt å forstå dei enklare algoritmane, fordi dei illustrerer grunnleggjande konsept som samanlikning, byting og iterasjon, og fordi dei er eit godt utgangspunkt for å forstå algoritmekompleksitet.

Oppsummering

I dette kapittelet har du lært:

- Lineaert søk: sjekkar kvart element i rekkefølge.
- Binaersoek: halverer soekeomraadet, krev sortert liste.
- Boblesortering: byter naboelement gjentekne gonger.
- Innsetjings- og utvalssortering: andre enkle sorteringsalgoritmar.
- Samanlikning: binaersoek er mykje raskare enn lineaert på store lister.

Noekkelbegreper