3.2 Søke- og sorteringsalgoritmer

Søke- og sorteringsalgoritmer

Søking og sortering er to av de mest grunnleggende operasjonene i programmering. Nesten alle programmer trenger å:
- Finne spesifikke data i en samling (søking)
- Organisere data i en bestemt rekkefølge (sortering)

I dette kapittelet skal du lære:
- Lineært søk og binærsøk
- Flere sorteringsalgoritmer og når de er nyttige
- Hvordan du analyserer og sammenligner algoritmer
- Pythons innebygde verktøy for søk og sortering

Disse algoritmene er fundamentale i informatikk og brukes i alt fra databaser til søkemotorer.

To hovedtyper:

1. Lineært søk (Sequential Search)
- Går gjennom elementene ett om gangen
- Fungerer på både sorterte og usorterte lister
- Tidskompleksitet: O(n)

2. Binærsøk (Binary Search)
- Deler søkeområdet i to for hver iterasjon
- Krever at listen er sortert
- Tidskompleksitet: O(log n)

Valg av algoritme:
- Små lister (< 100 elementer): Lineært søk er helt greit
- Usortert liste: Må bruke lineært søk
- Stor, sortert liste: Binærsøk er mye raskere
- Hvis du må sortere først: Vurder om sortering + binærsøk er verdt det

Lineært søk er den enkleste søkealgoritmen - vi går gjennom lista element for element til vi finner det vi leter etter.

Implementasjon:

def lineært_søk(liste, mål):
    """
    Søker etter mål i liste.
    Returnerer indeks hvis funnet, -1 hvis ikke funnet.
    """
    for i in range(len(liste)):
        if liste[i] == mål:
            return i
    return -1

# Test
tall = [4, 2, 7, 1, 9, 3]
print(lineært_søk(tall, 7))   # 2
print(lineært_søk(tall, 5))   # -1

Med Pythons innebygde metoder:

tall = [4, 2, 7, 1, 9, 3]

# Sjekk om element finnes
if 7 in tall:
    indeks = tall.index(7)
    print(f"Funnet på indeks {indeks}")

# index() kaster ValueError hvis ikke funnet
try:
    indeks = tall.index(5)
except ValueError:
    print("Ikke funnet")

Analyse:
- Best case: O(1) - elementet er først i listen
- Worst case: O(n) - elementet er sist eller ikke i listen
- Average case: O(n/2) = O(n) - må sjekke halvparten i gjennomsnitt

Fordeler:
- Enkel å implementere
- Fungerer på usorterte lister
- Ingen forberedelse nødvendig

Ulemper:
- Treg for store lister
- Må potensielt sjekke alle elementer

Binærsøk er mye raskere, men krever at listen er sortert. Strategien er å halvere søkeområdet for hver iterasjon.

Slik virker det:
1. Se på midterste element
2. Hvis det er målet: Ferdig!
3. Hvis målet er mindre: Søk i venstre halvdel
4. Hvis målet er større: Søk i høyre halvdel
5. Gjenta til elementet er funnet eller området er tomt

Implementasjon (iterativ):

def binærsøk(sortert_liste, mål):
    """
    Binærsøk i sortert liste.
    Returnerer indeks hvis funnet, -1 hvis ikke funnet.
    """
    venstre = 0
    høyre = len(sortert_liste) - 1

    while venstre <= høyre:
        midten = (venstre + høyre) // 2

        if sortert_liste[midten] == mål:
            return midten
        elif sortert_liste[midten] < mål:
            venstre = midten + 1  # Søk i høyre halvdel
        else:
            høyre = midten - 1    # Søk i venstre halvdel

    return -1

# Test
tall = [1, 2, 3, 4, 7, 9]  # MÅ være sortert!
print(binærsøk(tall, 7))   # 4
print(binærsøk(tall, 5))   # -1

Implementasjon (rekursiv):

def binærsøk_rekursiv(sortert_liste, mål, venstre=0, høyre=None):
    """Rekursiv versjon av binærsøk"""
    if høyre is None:
        høyre = len(sortert_liste) - 1

    if venstre > høyre:
        return -1

    midten = (venstre + høyre) // 2

    if sortert_liste[midten] == mål:
        return midten
    elif sortert_liste[midten] < mål:
        return binærsøk_rekursiv(sortert_liste, mål, midten + 1, høyre)
    else:
        return binærsøk_rekursiv(sortert_liste, mål, venstre, midten - 1)

Med Pythons bisect-modul:

import bisect

tall = [1, 2, 3, 4, 7, 9]

# Finn indeks hvor element skulle vært
indeks = bisect.bisect_left(tall, 7)
if indeks < len(tall) and tall[indeks] == 7:
    print(f"Funnet på indeks {indeks}")

Analyse:
- Tidskompleksitet: O(log n)
- Med 1000 elementer: Maks 10 sammenligninger (2¹⁰ = 1024)
- Med 1,000,000 elementer: Maks 20 sammenligninger (2²⁰ ≈ 1 million)

Eksempel på effektiviteten:

n = 100:      Lineært = 100, Binært = 7
n = 1,000:    Lineært = 1,000, Binært = 10
n = 1,000,000: Lineært = 1,000,000, Binært = 20

Binærsøk er dramatisk raskere, men husk: Listen MÅ være sortert først!

Du søker etter tallet 23 i denne sorterte listen med binærsøk:

[5, 12, 17, 23, 28, 31, 44, 56, 63, 71, 82]

Hvor mange sammenligninger må du gjøre?

Hovedkategorier:

Simple algoritmer (O(n²)):
- Bubble Sort - enklest å forstå, bytter naboer
- Selection Sort - finner minste element gjentatte ganger
- Insertion Sort - bygger sortert liste gradvis

Effektive algoritmer (O(n log n)):
- Merge Sort - del-og-hersk strategi
- Quick Sort - velger pivot og partisjonerer
- Heap Sort - bruker heap-datastruktur

Når brukes de?

Bubble Sort er den enkleste sorteringsalgoritmen. Den sammenligner naboelementer og bytter dem hvis de er i feil rekkefølge.

Slik virker det:
- Gå gjennom listen gjentatte ganger
- Sammenlign hvert par av naboer
- Bytt hvis de er i feil rekkefølge
- Etter første runde er største element "boblet" til slutten
- Gjenta til ingen bytter skjer

Implementasjon:

def bubble_sort(liste):
    """
    Sorterer liste med bubble sort.
    Endrer listen in-place.
    """
    n = len(liste)

    # Trenger maks n-1 runder
    for i in range(n - 1):
        # Flagg for å sjekke om noen bytter skjedde
        byttet = False

        # Gå gjennom usortert del
        for j in range(n - 1 - i):
            # Sammenlign naboelement
            if liste[j] > liste[j + 1]:
                # Bytt
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
                byttet = True

        # Hvis ingen bytter, er listen sortert
        if not byttet:
            break

    return liste

# Test
tall = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(tall))
# [11, 12, 22, 25, 34, 64, 90]

Visualisering av første runde:

Start:    [64, 34, 25, 12, 22, 11, 90]
Steg 1:   [34, 64, 25, 12, 22, 11, 90]  (byttet 64 og 34)
Steg 2:   [34, 25, 64, 12, 22, 11, 90]  (byttet 64 og 25)
Steg 3:   [34, 25, 12, 64, 22, 11, 90]  (byttet 64 og 12)
Steg 4:   [34, 25, 12, 22, 64, 11, 90]  (byttet 64 og 22)
Steg 5:   [34, 25, 12, 22, 11, 64, 90]  (byttet 64 og 11)
Steg 6:   [34, 25, 12, 22, 11, 64, 90]  (ingen bytt, 90 er største)

Analyse:
- Tidskompleksitet: O(n²) i verste og gjennomsnittlig case
- Best case: O(n) hvis listen allerede er sortert (med byttet-flagg)
- Plasskompleksitet: O(1) - sorterer in-place
- Stabil: Bevarer relativ rekkefølge for like elementer

Fordeler:
- Enkel å forstå og implementere
- Sorterer in-place (bruker lite minne)
- Oppdager når listen er sortert

Ulemper:
- Veldig treg for store lister
- Mange sammenligninger og bytter

Selection Sort finner det minste elementet og plasserer det først, deretter nest-minste osv.

Slik virker det:
1. Finn minste element i usortert del
2. Bytt det med første element i usortert del
3. Flytt grensen mellom sortert og usortert én plass
4. Gjenta til hele listen er sortert

Implementasjon:

def selection_sort(liste):
    """
    Sorterer liste med selection sort.
    Endrer listen in-place.
    """
    n = len(liste)

    # Gå gjennom hele listen
    for i in range(n - 1):
        # Finn minste element i usortert del
        min_indeks = i
        for j in range(i + 1, n):
            if liste[j] < liste[min_indeks]:
                min_indeks = j

        # Bytt minste element med første i usortert del
        liste[i], liste[min_indeks] = liste[min_indeks], liste[i]

    return liste

# Test
tall = [64, 25, 12, 22, 11]
print(selection_sort(tall))
# [11, 12, 22, 25, 64]

Visualisering:

Start:     [64, 25, 12, 22, 11]
           |<- usortert ->|

Runde 1:   [11, 25, 12, 22, 64]  (byttet 11 og 64)
           [S] |<-usortert->|

Runde 2:   [11, 12, 25, 22, 64]  (byttet 12 og 25)
           [  S  ] |<usort>|

Runde 3:   [11, 12, 22, 25, 64]  (byttet 22 og 25)
           [    S    ] |uso|

Runde 4:   [11, 12, 22, 25, 64]  (ingen bytt nødvendig)
           [      S      ] |u|

Ferdig:    [11, 12, 22, 25, 64]
           [    Sortert     ]

Analyse:
- Tidskompleksitet: O(n²) alltid (også best case!)
- Plasskompleksitet: O(1) - sorterer in-place
- Ikke stabil: Kan endre rekkefølge på like elementer

Sammenligninger: n(n-1)/2 = O(n²)
Bytter: Maks n (én per runde)

Fordeler:
- Minimalt antall bytter (n-1)
- Sorterer in-place
- Fungerer bra når writing er dyrt

Ulemper:
- Alltid O(n²), selv om listen er sortert
- Ikke stabil

Du skal sortere listen [5, 1, 4, 2, 8] med både bubble sort og selection sort.

Insertion Sort bygger en sortert liste gradvis ved å sette inn hvert element på riktig plass.

Analogi: Som å sortere spillkort i hånden - du tar ett kort om gangen og setter det inn på riktig plass blant kortene du allerede har sortert.

Slik virker det:
1. Start med første element (allerede "sortert")
2. Ta neste element
3. Finn riktig posisjon i sortert del
4. Skyv elementer til siden og sett inn
5. Gjenta for alle elementer

Implementasjon:

def insertion_sort(liste):
    """
    Sorterer liste med insertion sort.
    Endrer listen in-place.
    """
    for i in range(1, len(liste)):
        # Element som skal settes inn
        nøkkel = liste[i]

        # Finn riktig posisjon i sortert del
        j = i - 1
        while j >= 0 and liste[j] > nøkkel:
            # Skyv element én plass til høyre
            liste[j + 1] = liste[j]
            j -= 1

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

    return liste

# Test
tall = [12, 11, 13, 5, 6]
print(insertion_sort(tall))
# [5, 6, 11, 12, 13]

Visualisering:

Start:       [12, 11, 13, 5, 6]
             [S]  <- første element er sortert

Runde 1:     [11, 12, 13, 5, 6]
             [  S  ]  <- satt inn 11 før 12

Runde 2:     [11, 12, 13, 5, 6]
             [    S    ]  <- 13 allerede på rett plass

Runde 3:     [5, 11, 12, 13, 6]
             [      S      ]  <- 5 satt inn først

Runde 4:     [5, 6, 11, 12, 13]
             [        S        ]  <- 6 satt inn etter 5

Ferdig!

Analyse:
- Best case: O(n) - hvis listen allerede er sortert
- Average case: O(n²)
- Worst case: O(n²) - hvis listen er reversert
- Plasskompleksitet: O(1) - sorterer in-place
- Stabil: Ja

Fordeler:
- Enkel å implementere
- Effektiv for små datasett
- Effektiv for nesten sorterte data
- Sorterer in-place
- Stabil sortering
- Online: Kan sortere mens data mottas

Ulemper:
- O(n²) for store, usorterte datasett

Når er Insertion Sort best:

# Perfekt for nesten sortert data
nesten_sortert = [1, 2, 3, 5, 4, 6, 7]  # Bare ett element feil
# Insertion sort vil være O(n) her!

# Også bra for små lister
små_data = [3, 1, 4, 1, 5]
# Overhead fra mer komplekse algoritmer lønner seg ikke

Du har disse tre scenarioene:

A) Sortere en liste med 10 elementer
B) Sortere en liste med 10,000 elementer som nesten er sortert (bare 5 elementer feil)
C) Sortere en liste med 10,000 helt tilfeldige elementer

Hvilken enkel sorteringsalgoritme (Bubble, Selection, eller Insertion) ville du valgt for hver?

Prinsipp:
1. Del: Splitt listen i to like store halvdeler
2. Hersk: Sorter hver halvdel rekursivt
3. Kombiner: Slå sammen (merge) de to sorterte halvdelene

Egenskaper:
- Tidskompleksitet: O(n log n) for alle tilfeller
- Plasskompleksitet: O(n) - trenger ekstra minne
- Stabil: Bevarer rekkefølge for like elementer
- Ikke in-place: Lager nye lister underveis

Hvorfor O(n log n)?
- Vi deler listen i to log₂(n) ganger (det er høyden på rekursjons-treet)
- På hvert nivå slår vi sammen n elementer totalt
- Totalt: n × log₂(n) operasjoner

Visualisering:

Original:    [38, 27, 43, 3, 9, 82, 10]

Del:         [38, 27, 43, 3] [9, 82, 10]
             [38, 27] [43, 3] [9, 82] [10]
             [38] [27] [43] [3] [9] [82] [10]

Merge:       [27, 38] [3, 43] [9, 82] [10]
             [3, 27, 38, 43] [9, 10, 82]
             [3, 9, 10, 27, 38, 43, 82]

La oss implementere Merge Sort i Python:

Komplett implementasjon:

def merge_sort(liste):
    """
    Sorterer liste med merge sort.
    Returnerer ny sortert liste.
    """
    # Base case: Liste med 0 eller 1 element er allerede sortert
    if len(liste) <= 1:
        return liste

    # Del: Finn midtpunkt og splitt
    midten = len(liste) // 2
    venstre = liste[:midten]
    høyre = liste[midten:]

    # Hersk: Sorter hver halvdel rekursivt
    venstre = merge_sort(venstre)
    høyre = merge_sort(høyre)

    # Kombiner: Slå sammen sorterte halvdeler
    return merge(venstre, høyre)


def merge(venstre, høyre):
    """
    Slår sammen to sorterte lister til én sortert liste.
    """
    resultat = []
    i = j = 0

    # Sammenlign elementer fra begge listene
    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

    # Legg til resterende elementer
    resultat.extend(venstre[i:])
    resultat.extend(høyre[j:])

    return resultat


# Test
tall = [38, 27, 43, 3, 9, 82, 10]
sortert = merge_sort(tall)
print(sortert)
# [3, 9, 10, 27, 38, 43, 82]

Steg-for-steg med små data:

# Sorter [3, 1, 4, 2]

def merge_sort_verbose(liste, dybde=0):
    """Merge sort med debug-output"""
    indent = "  " * dybde
    print(f"{indent}Sorterer: {liste}")

    if len(liste) <= 1:
        print(f"{indent}Base case: {liste}")
        return liste

    midten = len(liste) // 2
    venstre = merge_sort_verbose(liste[:midten], dybde + 1)
    høyre = merge_sort_verbose(liste[midten:], dybde + 1)

    resultat = merge(venstre, høyre)
    print(f"{indent}Merged: {resultat}")
    return resultat

merge_sort_verbose([3, 1, 4, 2])

Output:

Sorterer: [3, 1, 4, 2]
  Sorterer: [3, 1]
    Sorterer: [3]
    Base case: [3]
    Sorterer: [1]
    Base case: [1]
  Merged: [1, 3]
  Sorterer: [4, 2]
    Sorterer: [4]
    Base case: [4]
    Sorterer: [2]
    Base case: [2]
  Merged: [2, 4]
Merged: [1, 2, 3, 4]

Analyse av merge-funksjonen:
- Går gjennom begge listene nøyaktig én gang
- Tidskompleksitet: O(n) hvor n = total lengde
- Alltid lineær tid for å merge

Fordeler med Merge Sort:
- Garantert O(n log n) - ingen worst case
- Stabil sortering
- Godt for lenkelister
- Paralleliserbar

Ulemper:
- Trenger O(n) ekstra minne
- Litt tregere enn Quick Sort i praksis (flere kopieringer)

Du kjører merge_sort() på en liste med 8 elementer: [8, 3, 5, 4, 7, 6, 1, 2]

Python har innebygde, høyt optimaliserte verktøy for sortering:

sorted() - Funksjon

# Returnerer ny sortert liste, original uendret
tall = [3, 1, 4, 1, 5]
sortert = sorted(tall)
print(tall)     # [3, 1, 4, 1, 5] - uendret
print(sortert)  # [1, 1, 3, 4, 5]

.sort() - Metode

# Sorterer listen in-place, returnerer None
tall = [3, 1, 4, 1, 5]
tall.sort()
print(tall)  # [1, 1, 3, 4, 5]

Nøkkelparametre:

reverse - Synkende rekkefølge:

tall = [3, 1, 4, 1, 5]
print(sorted(tall, reverse=True))  # [5, 4, 3, 1, 1]

key - Egendefinert sorteringsnøkkel:

# Sorter etter lengde
ord = ["eple", "banan", "kiwi", "jordbær"]
print(sorted(ord, key=len))
# ['kiwi', 'eple', 'banan', 'jordbær']

# Sorter personer etter alder
personer = [
    {"navn": "Anna", "alder": 25},
    {"navn": "Bob", "alder": 20},
    {"navn": "Charlie", "alder": 30}
]
sortert = sorted(personer, key=lambda p: p["alder"])
# Bob (20), Anna (25), Charlie (30)

Timsort - Pythons algoritme:
- Hybrid av merge sort og insertion sort
- O(n log n) worst case
- O(n) best case for nesten sorterte data
- Stabil sortering
- Optimalisert i C

Når bruke hva:
- .sort(): Når du vil endre eksisterende liste
- sorted(): Når du trenger ny liste eller skal sortere annen iterable
- Egne algoritmer: Kun for læring eller svært spesielle tilfeller

Du har en liste med studenter:

studenter = [
    {"navn": "Emma", "karakter": 4, "alder": 18},
    {"navn": "Oliver", "karakter": 5, "alder": 19},
    {"navn": "Sofie", "karakter": 4, "alder": 18},
    {"navn": "Lucas", "karakter": 6, "alder": 18}
]

Du vil sortere først etter karakter (høyest først), deretter etter navn alfabetisk hvis karakterene er like.

Oppsummering

Søkealgoritmer:

Stabil sortering:

- Bevarer rekkefølge for elementer med samme verdi
- Viktig når du sorterer på flere kriterier
In-place vs ny liste:
- In-place: Endrer original, bruker O(1) ekstra minne
- Ny liste: Original uendret, bruker O(n) ekstra minne
Trade-offs:
- Tid vs minne (merge sort bruker mer minne, men garantert rask)

- Enkelt vs effektivt (bubble sort er enkel, men treg)

- Generelt vs spesialisert (insertion sort er best for nesten sorterte data)
Praktiske råd:
1. Bruk Pythons sorted() og .sort() i produksjonskode

2. Forstå algoritmene for å kunne velge riktig i spesielle tilfeller
3. Profiler før du optimaliserer
4. Binærsøk krever sortert data - vurder om sortering lønner seg

Samleoppgaver

Oppgaver som kombinerer søk, sortering og analyse:

Medianen er det midterste tallet i en sortert liste. For en usortert liste må vi:
1. Sortere listen
2. Finne midterste element(ene)

Hvis listen har n elementer:
- Oddetall: Median = liste[n//2]
- Partall: Median = (liste[n//2-1] + liste[n//2]) / 2

Hva er tidskompleksiteten for å finne medianen i en usortert liste?

Du har en usortert liste med n elementer. Du skal søke etter k forskjellige elementer.

Hvilken strategi er best?

A) Bruk lineært søk for hvert element (k × n sammenligninger)
B) Sorter først, deretter binærsøk (n log n + k log n sammenligninger)

Implementer en funksjon som sorterer en liste med komplekse objekter ved å bruke bubble sort, men med en egendefinert sammenlignings-funksjon.

class Person:
    def __init__(self, navn, alder):
        self.navn = navn
        self.alder = alder

    def __repr__(self):
        return f"{self.navn}({self.alder})"

personer = [
    Person("Anna", 25),
    Person("Bob", 20),
    Person("Charlie", 30),
    Person("Diana", 20)
]

Sorter først etter alder, deretter alfabetisk etter navn hvis alderen er lik.