3.4 Søke- og sorteringsalgoritmer

Telefonkatalogen med 10 000 navn

Tenk deg en telefonkatalog med 10 000 navn. Skal du finne «Olsen», kan du sjekke hvert navn fra begynnelsen – men det er ikke slik du gjør det. Du slår opp midt i boka, ser at du er på «M», og vet at «O» er litt bak. Så halverer du igjen og igjen til du finner riktig side. Denne intuitive metoden er en av informatikkens viktigste algoritmer: binærsøk.

Nesten alle programmer må søke i og sortere data. La oss starte med den enkleste søkemetoden, lineært søk (også kalt sekvensielt søk). Den starter fra begynnelsen og sjekker hvert element i rekkefølge til den finner det den leter etter eller har gått gjennom hele listen. Det fine er at den fungerer på alle lister, sorterte eller ikke:

def lineaert_sok(liste, sokeord):
    for i in range(len(liste)):
        if liste[i] == sokeord:
            return i
    return -1

Ulempen er farten. For en liste med n elementer må lineært søk i snitt sjekke n/2 elementer, og i verste fall alle n. Vi sier at den har tidskompleksitet O(n). For en million elementer kan det bety en million sammenligninger.

Da er binærsøk dramatisk bedre – men det krever at listen er sortert. Algoritmen ser på midtelementet: er det du søker mindre, fortsetter du i venstre halvdel; er det større, i høyre. Slik halveres søkeområdet hvert steg:

def binaersok(sortert_liste, sokeord):
    lav, hoy = 0, len(sortert_liste) - 1
    while lav <= hoy:
        midt = (lav + hoy) // 2
        if sortert_liste[midt] == sokeord:
            return midt
        elif sortert_liste[midt] < sokeord:
            lav = midt + 1
        else:
            hoy = midt - 1
    return -1

Binærsøk trenger maksimalt log₂(n) sammenligninger. For en million elementer holder det med rundt 20 – mot en million for lineært søk.

Tre måter å sortere på

For å bruke binærsøk må listen være sortert – så hvordan sorterer vi? Det finnes mange algoritmer, og tre enkle er verdt å forstå.

Boblesortering er enklest å forstå. Du går gjennom listen og bytter naboelementer som står i feil rekkefølge, om og om igjen til ingenting trenger å byttes. Navnet kommer av at de største elementene gradvis «bobler opp» til riktig plass, som luftbobler i et glass. En liten optimalisering er å stoppe så snart en hel gjennomgang ikke gjør noen bytter – da er listen sortert.

Innsettingssortering fungerer som når du sorterer kort på hånden: du tar ett kort om gangen og setter det inn på riktig plass blant kortene du allerede holder sortert. Du sammenligner det nye elementet med dem til venstre, flytter de større ett hakk til høyre, og setter inn på rett plass. Denne er spesielt effektiv for lister som allerede er nesten sorterte, fordi den da gjør svært få flyttinger.

Utvalgssortering har en annen idé: finn det minste elementet og plasser det først, finn så det nest minste og plasser det på plass nummer to, og så videre. Den gjør alltid nøyaktig like mange sammenligninger uansett om listen er sortert fra før, men til gjengjeld få bytteoperasjoner. Felles for alle tre er at de bytter, sammenligner og itererer – de grunnleggende byggesteinene i sortering.

Hvorfor valget av algoritme betyr alt

Når vi sammenligner, ser vi hvor stor forskjell algoritmevalg gjør. Blant søkealgoritmene gjør lineært søk opptil n sammenligninger, mens binærsøk klarer seg med log₂(n) – men binærsøk krever en sortert liste. I en liste med en million elementer betyr det opptil en million sammenligninger mot maksimalt 20.

For sorteringsalgoritmene er bildet dystrere. Alle de tre enkle – bobles-, innsettings- og utvalgssortering – har tidskompleksitet O(n²) i verste fall. Det betyr at hvis listen blir ti ganger så stor, blir arbeidet rundt hundre ganger så stort. Derfor bruker man i praksis aldri disse på store datasett. I stedet bruker du Pythons innebygde sorted() eller metoden .sort(), som bygger på algoritmen Timsort med tidskompleksitet O(n log n) – mye raskere:

tall = [64, 34, 25, 12, 22, 11, 90]
sortert = sorted(tall)  # ny sortert liste
tall.sort()             # sorterer på plass

Likevel er det verdifullt å forstå de enkle algoritmene, fordi de illustrerer grunnkonseptene og er et godt utgangspunkt for å forstå algoritmekompleksitet. Til slutt kan du kombinere alt: les inn en liste med elevnavn, sorter den med innsettingssortering, og la brukeren søke med binærsøk. Bruk .lower() i sammenligningene, så blir både sortering og søk uavhengig av store og små bokstaver.

Oppsummering

Vi startet i telefonkatalogen og endte med å forstå hvorfor algoritmevalg er avgjørende. Lineært søk sjekker hvert element (O(n)) og fungerer på alle lister, mens binærsøk halverer søkeområdet (log₂(n)), men krever en sortert liste.

For sortering så vi tre enkle metoder: boblesortering bytter naboelementer, innsettingssortering setter hvert element inn på rett plass (best for nesten sorterte lister), og utvalgssortering plukker ut det minste om gangen. Alle tre er O(n²) og trege for store mengder – derfor bruker du i praksis Pythons sorted() med Timsort (O(n log n)). Men å forstå de enkle algoritmene gir deg grunnlaget for å tenke på effektivitet, som er kjernen i neste tema: algoritmekompleksitet.