3.4 Søke- og sorteringsalgoritmer

Søke- og sorteringsalgoritmer

Tenk deg at du har en telefonkatalog med 10 000 navn. Hvis du skal finne nummeret til «Olsen», kan du starte fra begynnelsen og sjekke hvert navn. Men det er jo ikke slik du faktisk bruker en telefonkatalog. Du slår opp omtrent midt i boken, ser at du er på «M», og vet at «O» er litt lenger bak. Deretter halverer du igjen og igjen til du finner riktig side. Denne intuitive metoden er faktisk en av de viktigste algoritmene i informatikk: binærsøk.

Søking og sortering er to av de mest grunnleggende operasjonene i informatikk. Praktisk talt alle programmer som arbeider med data, må søke i data og sortere data. E-postprogrammet ditt sorterer meldinger etter dato. Nettbutikken sorterer produkter etter pris. Søkemotorer søker gjennom milliarder av nettsider for å finne det du leter etter.

I dette kapittelet skal du lære å implementere de mest kjente søke- og sorteringsalgoritmene i Python, forstå hvordan de fungerer, og sammenligne dem med hensyn til effektivitet.

Lineært søk

Lineært søk er som å lete etter en bestemt bok i en usortert bokhylle. Du begynner med den første boken, sjekker om det er riktig bok, og hvis ikke, går du videre til neste. Du fortsetter til du finner boken eller har sjekket alle.

Algoritme:
1. Start fra det første elementet i listen
2. Sammenlign elementet med det du søker etter
3. Hvis det er likt, returner posisjonen
4. Hvis ikke, gå til neste element
5. Hvis du har sjekket alle elementer uten å finne, returner «ikke funnet»

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 en liste med n elementer må lineært søk i gjennomsnitt sjekke n/2 elementer, og i verste fall alle n. Vi sier at lineært søk har tidskompleksitet O(n), der n er antall elementer. For en liste med 1 000 000 elementer kan det ta opptil 1 000 000 sammenligninger.

Binærsøk

Binærsøk er som å slå opp i en telefonkatalog. Fordi navnene er sortert alfabetisk, kan du halvere søkeområdet i hvert steg.

Algoritme:
1. Sett lav til 0 og hoy til siste indeks
2. Finn midt = (lav + hoy) // 2
3. Hvis elementet på midt er det du søker, returner midt
4. Hvis elementet på midt er for stort, sett hoy = midt - 1
5. Hvis elementet på midt er for lite, sett lav = midt + 1
6. Gjenta fra steg 2 så lenge lav <= hoy
7. Hvis lav > hoy, er elementet ikke i listen

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 enkleste sorteringsalgoritmen å forstå. Ideen er å gjentatte ganger gå gjennom listen og sammenligne naboelementer. Hvis to naboelementer er i feil rekkefølge, bytter vi dem. Vi gjentar dette til listen er sortert.

Navnet «boblesortering» kommer av at de største elementene gradvis «bobler opp» til riktig posisjon, akkurat som luftbobler stiger til overflaten i et glass vann.

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 bobler 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 bytter, ferdig!)

Boblesortering er enkel og intuitiv, men den er treg for store datasett fordi den i verste fall trenger omtrent n² sammenligninger.

Innsettingssortering (Insertion Sort)

Innsettingssortering fungerer som du sorterer spillkort på hånden. Du tar ett kort om gangen fra bunken og setter det inn på riktig plass blant de kortene du allerede holder sortert.

Algoritme:
1. Start med det andre elementet (det første er «sortert» alene)
2. Ta elementet og sammenlign det med elementene til venstre
3. Flytt elementene som er større ett steg til høyre
4. Sett inn elementet på riktig plass
5. Gjenta for alle gjenværende elementer

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

Utvalgssortering (Selection Sort)

Utvalgssortering er en annen 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å videre.

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

Sammenligning av søke- og sorteringsalgoritmer

Søkealgoritmer:

Alle tre sorteringsalgoritmene har tidskompleksitet O(n²) i verste fall, noe som betyr at de blir svært trege for store datamengder. I praksis bruker Python den innebygde funksjonen sorted() eller metoden .sort(), som bruker Timsort-algoritmen med tidskompleksitet O(n log n), noe som er vesentlig raskere.

# 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å de enklere algoritmene, fordi de illustrerer grunnleggende konsepter som sammenligning, bytting og iterasjon, og fordi de er et godt utgangspunkt for å forstå algoritmekompleksitet.

Oppsummering

I dette kapittelet har du lært:

- Lineært søk: sjekker hvert element i rekkefølge.
- Binærsøk: halverer søkeområdet, krever sortert liste.
- Boblesortering: bytter naboelementer gjentatte ganger.
- Innsettings- og utvalgssortering: andre enkle sorteringsalgoritmer.
- Sammenligning: binærsøk er mye raskere enn lineært på store lister.

Noekkelbegreper