3.2 Søke- og sorteringsalgoritmer

Å finne og å ordne

Søking og sortering er to av de mest grunnleggende operasjonene i programmering. Nesten alle programmer trenger å finne data i en samling og å organisere dem i en bestemt rekkefølge. Disse algoritmene driver alt fra databaser til søkemotorer.

La oss starte med søk. Den enkleste metoden er lineært søk: du går gjennom listen element for element til du finner det du leter etter. Det fungerer på både sorterte og usorterte lister, men det er O(n) – i verste fall må du sjekke alt. I beste fall, hvis elementet ligger først, er det O(1).

Den langt raskere metoden er binærsøk, men den krever at listen er sortert. Idéen er å halvere søkeområdet hver gang. Du ser på det midterste elementet: er det målet, er du ferdig; er målet mindre, leter du i venstre halvdel; er det større, i høyre. Slik fortsetter du til du finner elementet eller området er tomt:

def binærsøk(liste, mål):
    venstre, høyre = 0, len(liste) - 1
    while venstre <= høyre:
        midten = (venstre + høyre) // 2
        if liste[midten] == mål:
            return midten
        elif liste[midten] < mål:
            venstre = midten + 1
        else:
            høyre = midten - 1
    return -1

Binærsøk er O(log n). Med en million elementer trenger lineært søk opptil en million sammenligninger – binærsøk klarer seg med rundt 20.

De enkle sorteringene

En sorteringsalgoritme ordner elementer i en bestemt rekkefølge. Tre klassiske enkle algoritmer er alle O(n²), men lærer oss mye. Bubble sort sammenligner naboelementer og bytter dem hvis de står feil; etter første runde har det største elementet «boblet» til slutten. Med et byttet-flagg kan den oppdage en sortert liste og stoppe tidlig, noe som gir O(n) i beste fall. Selection sort finner det minste elementet i den usorterte delen og bytter det fram; den gjør få bytter – bare ett per runde – men er alltid O(n²), også på en allerede sortert liste. Insertion sort bygger den sorterte delen gradvis, som når du ordner spillkort i hånden: du tar ett kort om gangen og setter det inn på riktig plass.

Forskjellene betyr noe i praksis. Selection sort gjør færrest bytter, noe som er en fordel når selve flyttingen er dyr. Insertion sort er strålende for nesten sorterte data, der den nærmer seg O(n), og for små lister. Det finnes også begrepet stabil sortering: en stabil algoritme bevarer den relative rekkefølgen til elementer med lik verdi. Bubble og insertion sort er stabile; selection sort er ikke. Stabilitet blir viktig når du sorterer på flere kriterier etter hverandre. Men felles for alle tre: for store, tilfeldige datasett er O(n²) altfor tregt – da bør du strekke deg etter noe bedre.

Merge sort og del-og-hersk

For virkelig effektiv sortering trenger vi en smartere strategi. Merge sort bruker del-og-hersk (divide and conquer) og garanterer O(n log n) i alle tilfeller. Den jobber i tre trinn: del listen i to like halvdeler, hersk ved å sortere hver halvdel rekursivt, og kombiner ved å flette de to sorterte halvdelene sammen. Flettingen, merge, går gjennom begge listene én gang og plukker det minste fronten-elementet hver gang:

def merge(venstre, høyre):
    resultat = []
    i = j = 0
    while i < len(venstre) and j < len(høyre):
        if venstre[i] <= høyre[j]:
            resultat.append(venstre[i]); i += 1
        else:
            resultat.append(høyre[j]); j += 1
    resultat.extend(venstre[i:]); resultat.extend(høyre[j:])
    return resultat

Hvorfor O(n log n)? Vi deler listen i to omtrent log₂(n) ganger, og på hvert nivå flettes n elementer til sammen. For n elementer kalles merge totalt n−1 ganger, fordi vi starter med n enkeltelement-lister og ender med én sortert liste. Merge sort er stabil og har garantert ytelse uten noe dårlig worst case, men den krever O(n) ekstra minne fordi den lager nye lister underveis. Det er prisen for forutsigbarheten.

Pythons egen sortering vinner nesten alltid

I praksis trenger du sjelden å skrive disse algoritmene selv. Python har innebygde, høyt optimaliserte verktøy. Funksjonen sorted(liste) returnerer en ny sortert liste og lar originalen være urørt, mens metoden liste.sort() sorterer in-place og returnerer None. Begge tar nyttige parametere: reverse=True for synkende rekkefølge, og key for en egendefinert sorteringsnøkkel. Vil du sortere ord etter lengde, bruker du key=len; vil du sortere personer etter alder, bruker du key=lambda p: p["alder"].

Flere kriterier løses elegant med en tuppel som nøkkel. Skal studenter sorteres etter karakter (høyest først) og deretter navn alfabetisk, skriver du key=lambda s: (-s["karakter"], s["navn"]) – minustegnet snur karakteren til synkende, og navnet bryter likhet. Dette fungerer fordi Python sammenligner tupler element for element.

Bak sorted ligger Timsort, en hybrid av merge sort og insertion sort. Den er O(n log n) i verste fall, O(n) for nesten sorterte data, stabil, og skrevet i C – altså ekstremt rask. Konklusjonen er enkel: bruk sorted() og .sort() i praktisk kode. Skriv egne algoritmer kun for læring eller helt spesielle tilfeller. Og husk et tredje triks: for mange medlemskapssjekker kan du gjøre listen om til en mengde (set), som gir O(1)-oppslag og ofte slår både lineært søk og sortering-pluss-binærsøk.

Oppsummering

Vi lærte å finne og å ordne. For søk er lineært søk O(n) og fungerer på alt, mens binærsøk er O(log n) men krever en sortert liste – forskjellen er en million mot tjue sammenligninger på store data. For sortering møtte vi tre enkle O(n²)-algoritmer: bubble sort (stabil, kan stoppe tidlig), selection sort (få bytter, men alltid O(n²)) og insertion sort (stabil og rask på nesten sorterte data). Merge sort bruker del-og-hersk for garantert O(n log n), men koster O(n) ekstra minne.

Vi lærte også om stabil sortering, som bevarer rekkefølgen til like elementer. I praksis er konklusjonen klar: bruk Pythons sorted() og .sort(), drevet av den optimaliserte Timsort, og skriv egne algoritmer bare for læring. For mange medlemskapssjekker er en mengde ofte raskest av alt. I neste kapittel ser vi nærmere på flere datastrukturer.