3.2 Søke- og sorteringsalgoritmer

Søkje- og sorteringsalgoritmar

Søking og sortering er to av dei mest grunnleggjande operasjonane i programmering. Nesten alle program treng å:
- Finne spesifikke data i ei samling (søking)
- Organisere data i ei bestemt rekkjefølgje (sortering)

I dette kapittelet skal du lære:
- Lineært søk og binærsøk
- Fleire sorteringsalgoritmar og når dei er nyttige
- Korleis du analyserer og samanliknar algoritmar
- Pythons innebygde verktøy for søk og sortering

Desse algoritmane er fundamentale i informatikk og blir brukte i alt frå databasar til søkjemotorar.

To hovudtypar:

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

2. Binærsøk (Binary Search)
- Deler søkjeområdet i to for kvar iterasjon
- Krev at lista er sortert
- Tidskompleksitet: O(log n)

Val av algoritme:
- Små lister (< 100 element): Lineært søk er heilt greitt
- Usortert liste: Må bruke lineært søk
- Stor, sortert liste: Binærsøk er mykje raskare
- Viss du må sortere først: Vurder om sortering + binærsøk er verdt det

Lineært søk er den enklaste søkjealgoritmen - vi går gjennom lista element for element til vi finn det vi leitar 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 metodar:

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 lista
- Worst case: O(n) - elementet er sist eller ikkje i lista
- Average case: O(n/2) = O(n) - må sjekke halvparten i gjennomsnitt

Fordelar:
- Enkel å implementere
- Fungerer på usorterte lister
- Inga førebuing nødvendig

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

Binærsøk er mykje raskare, men krev at lista er sortert. Strategien er å halvere søkjeområdet for kvar iterasjon.

Slik verkar det:
1. Sjå på midtarste element
2. Viss det er målet: Ferdig!
3. Viss målet er mindre: Søk i venstre halvdel
4. Viss målet er større: Søk i høgre halvdel
5. Gjenta til elementet er funne 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 element: Maks 10 samanlikningar (2¹⁰ = 1024)
- Med 1,000,000 element: Maks 20 samanlikningar (2²⁰ ≈ 1 million)

Døme 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 raskare, men hugs: Lista MÅ vere sortert først!

Du søkjer etter talet 23 i denne sorterte lista med binærsøk:

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

Kor mange samanlikningar må du gjere?

Hovudkategoriar:

Simple algoritmar (O(n²)):
- Bubble Sort - enklast å forstå, byter naboar
- Selection Sort - finn minste element gjentekne gonger
- Insertion Sort - byggjer sortert liste gradvis

Effektive algoritmar (O(n log n)):
- Merge Sort - del-og-hersk-strategi
- Quick Sort - vel pivot og partisjonerer
- Heap Sort - brukar heap-datastruktur

Når blir dei brukte?

Bubble Sort er den enklaste sorteringsalgoritmen. Han samanliknar naboelement og byter dei viss dei er i feil rekkjefølgje.

Slik verkar det:
- Gå gjennom lista gjentekne gonger
- Samanlikn kvart par av naboar
- Byt viss dei er i feil rekkjefølgje
- Etter første runde er det største elementet "bobla" til slutten
- Gjenta til ingen byte 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 gjennomsnittleg case
- Best case: O(n) viss lista alt er sortert (med byttet-flagg)
- Plasskompleksitet: O(1) - sorterer in-place
- Stabil: Bevarer relativ rekkjefølgje for like element

Fordelar:
- Enkel å forstå og implementere
- Sorterer in-place (brukar lite minne)
- Oppdagar når lista er sortert

Ulemper:
- Veldig treg for store lister
- Mange samanlikningar og byte

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

Slik verkar det:
1. Finn minste element i usortert del
2. Byt det med første element i usortert del
3. Flytt grensa mellom sortert og usortert éin plass
4. Gjenta til heile lista 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 (òg best case!)
- Plasskompleksitet: O(1) - sorterer in-place
- Ikkje stabil: Kan endre rekkjefølgje på like element

Samanlikningar: n(n-1)/2 = O(n²)
Byte: Maks n (éin per runde)

Fordelar:
- Minimalt tal byte (n-1)
- Sorterer in-place
- Fungerer bra når writing er dyrt

Ulemper:
- Alltid O(n²), sjølv om lista er sortert
- Ikkje stabil

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

Insertion Sort byggjer ei sortert liste gradvis ved å setje inn kvart element på rett plass.

Analogi: Som å sortere spelkort i handa - du tek eitt kort om gongen og set det inn på rett plass blant korta du alt har sortert.

Slik verkar det:
1. Start med første element (alt "sortert")
2. Ta neste element
3. Finn rett posisjon i sortert del
4. Skyv element til sida og set inn
5. Gjenta for alle element

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) - viss lista alt er sortert
- Average case: O(n²)
- Worst case: O(n²) - viss lista er reversert
- Plasskompleksitet: O(1) - sorterer in-place
- Stabil: Ja

Fordelar:
- Enkel å implementere
- Effektiv for små datasett
- Effektiv for nesten sorterte data
- Sorterer in-place
- Stabil sortering
- Online: Kan sortere medan data blir mottekne

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 desse tre scenarioa:

A) Sortere ei liste med 10 element
B) Sortere ei liste med 10,000 element som nesten er sortert (berre 5 element feil)
C) Sortere ei liste med 10,000 heilt tilfeldige element

Kva for ein enkel sorteringsalgoritme (Bubble, Selection, eller Insertion) ville du valt for kvart?

Prinsipp:
1. Del: Splitt lista i to like store halvdelar
2. Hersk: Sorter kvar halvdel rekursivt
3. Kombiner: Slå saman (merge) dei to sorterte halvdelane

Eigenskapar:
- Tidskompleksitet: O(n log n) for alle tilfelle
- Plasskompleksitet: O(n) - treng ekstra minne
- Stabil: Bevarer rekkjefølgje for like element
- Ikkje in-place: Lagar nye lister undervegs

Kvifor O(n log n)?
- Vi deler lista i to log₂(n) gonger (det er høgda på rekursjons-treet)
- På kvart nivå slår vi saman n element totalt
- Totalt: n × log₂(n) operasjonar

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]

Lat 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 éin gong
- Tidskompleksitet: O(n) der n = total lengd
- Alltid lineær tid for å merge

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

Ulemper:
- Treng O(n) ekstra minne
- Litt tregare enn Quick Sort i praksis (fleire kopieringar)

Du køyrer merge_sort() på ei liste med 8 element: [8, 3, 5, 4, 7, 6, 1, 2]

Python har innebygde, høgt 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økkelparametrar:

reverse - Synkande rekkjefølgje:

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

key - Eigendefinert 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 kva:
- .sort(): Når du vil endre eksisterande liste
- sorted(): Når du treng ny liste eller skal sortere ein annan iterable
- Eigne algoritmar: Berre for læring eller svært spesielle tilfelle

Du har ei liste med studentar:

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øgast først), deretter etter namn alfabetisk viss karakterane er like.

Oppsummering

Søkjealgoritmar:

Stabil sortering:

- Bevarer rekkjefølgje for element med same verdi
- Viktig når du sorterer på fleire kriterium
In-place vs ny liste:
- In-place: Endrar original, brukar O(1) ekstra minne
- Ny liste: Original uendra, brukar O(n) ekstra minne
Trade-offs:
- Tid vs minne (merge sort brukar meir 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å algoritmane for å kunne velje rett i spesielle tilfelle
3. Profiler før du optimaliserer
4. Binærsøk krev sortert data - vurder om sortering lønner seg

Samleoppgåver

Oppgåver som kombinerer søk, sortering og analyse:

Medianen er det midtarste talet i ei sortert liste. For ei usortert liste må vi:
1. Sortere lista
2. Finne midtarste element(a)

Viss lista har n element:
- Oddetal: Median = liste[n//2]
- Partal: Median = (liste[n//2-1] + liste[n//2]) / 2

Kva er tidskompleksiteten for å finne medianen i ei usortert liste?

Du har ei usortert liste med n element. Du skal søkje etter k forskjellige element.

Kva for ein strategi er best?

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

Implementer ein funksjon som sorterer ei liste med komplekse objekt ved å bruke bubble sort, men med ein eigendefinert samanliknings-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 namn viss alderen er lik.