21 Datastrukturer og algoritmer

Lister og arrays

Lister i Python
Ei liste er ei ordna samling av element som kan endrast (mutable).

# Opprette lister
sensorer = [23.5, 24.1, 22.8, 25.0]
navn = ["sensor1", "sensor2", "sensor3"]
blandet = [1, "tekst", 3.14, True]

# Tilgang til elementer (0-indeksert)
print(sensorer[0])   # 23.5 (første element)
print(sensorer[-1])  # 25.0 (siste element)

# Endre element
sensorer[1] = 24.5

# Legge til elementer
sensorer.append(26.0)     # Legger til på slutten
sensorer.insert(0, 22.0)  # Setter inn på posisjon 0

# Fjerne elementer
sensorer.remove(22.8)     # Fjerner første forekomst
siste = sensorer.pop()    # Fjerner og returnerer siste

# Lengde
print(len(sensorer))

Slicing (utsnitt)

tall = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(tall[2:5])   # [2, 3, 4] (fra indeks 2 til 5-1)
print(tall[:3])    # [0, 1, 2] (fra start til 3-1)
print(tall[7:])    # [7, 8, 9] (fra 7 til slutt)
print(tall[::2])   # [0, 2, 4, 6, 8] (annethvert element)

Ordbøker (dictionaries)

Ordbøker lagrar data som nøkkel-verdi par. Rask oppslag basert på nøkkel.

# Opprette ordbok
sensor_data = {
    "temperatur": 23.5,
    "fuktighet": 65,
    "trykk": 1013.25,
    "enhet": "celsius"
}

# Tilgang til verdier
print(sensor_data["temperatur"])  # 23.5
print(sensor_data.get("vind", 0)) # 0 (standardverdi hvis ikke funnet)

# Legge til / endre
sensor_data["vind"] = 5.2
sensor_data["temperatur"] = 24.0

# Sjekke om nøkkel finnes
if "fuktighet" in sensor_data:
    print("Fuktighet funnet!")

# Iterere
for nokkel, verdi in sensor_data.items():
    print(f"{nokkel}: {verdi}")

# Nøstede ordbøker
vaerstasjon = {
    "stasjon1": {"temp": 22, "fukt": 60},
    "stasjon2": {"temp": 25, "fukt": 55}
}
print(vaerstasjon["stasjon1"]["temp"])  # 22

Når bruke liste vs ordbok?
- Liste: Ordna element, numerisk indeks, iterering
- Ordbok: Nøkkel-oppslag, skildrande nøklar, strukturerte data

Søkjealgoritmar

Lineært søk
Går gjennom lista element for element til vi finn det vi leitar etter.

def lineart_sok(liste, verdi):
    for i, element in enumerate(liste):
        if element == verdi:
            return i  # Fant på posisjon i
    return -1  # Ikke funnet

tall = [5, 2, 8, 1, 9, 3]
pos = lineart_sok(tall, 8)  # Returnerer 2

Kompleksitet: O(n) - i verste fall må vi sjekke alle n element.

Binært søk
Krev sortert liste. Halverer søkjeområdet for kvar iterasjon.

def binaert_sok(sortert_liste, verdi):
    lav = 0
    hoy = len(sortert_liste) - 1

    while lav <= hoy:
        midt = (lav + hoy) // 2
        if sortert_liste[midt] == verdi:
            return midt
        elif sortert_liste[midt] < verdi:
            lav = midt + 1
        else:
            hoy = midt - 1
    return -1

tall = [1, 2, 3, 5, 8, 9]  # MÅ være sortert!
pos = binaert_sok(tall, 5)  # Returnerer 3

Kompleksitet: O(log n) - mykje raskare for store lister!

Samanlikning:
- 1000 element: Lineært ~500 samanlikningar, binært ~10
- 1 000 000 element: Lineært ~500 000, binært ~20

Sorteringsalgoritmar

Boblesortering (Bubble Sort)
Samanliknar naboelement og byter viss dei er i feil rekkjefølgje. Gjenta til sortert.

def boblesortering(liste):
    n = len(liste)
    for i in range(n):
        for j in range(0, n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
    return liste

tall = [64, 34, 25, 12, 22, 11, 90]
sortert = boblesortering(tall.copy())
# [11, 12, 22, 25, 34, 64, 90]

Kompleksitet: O(n²) - treg for store lister

Innebygd sortering
Python har effektiv innebygd sortering:

tall = [64, 34, 25, 12]

# sorted() returnerer ny sortert liste
sortert = sorted(tall)

# .sort() sorterer listen "in-place"
tall.sort()

# Sortere i synkende rekkefølge
tall.sort(reverse=True)

# Sortere etter egendefinert nøkkel
sensorer = [("A", 25), ("B", 18), ("C", 30)]
sensorer.sort(key=lambda x: x[1])  # Sorterer etter temperatur
# [('B', 18), ('A', 25), ('C', 30)]

Kompleksitet:
- Boblesortering: O(n²)
- Python sort (Timsort): O(n log n)
- For 1000 element: Boble ~1 000 000 operasjonar, Timsort ~10 000