Sortering og søgning

Programmering B · HTX · B-niveau · Datastrukturer og algoritmer

💻 Sortering og søgning

Søgning — find et element i en samling:

Lineær søgning O(n): tjek hvert element en ad gangen.

```python

def linear_søg(liste, mål):

for i, element in enumerate(liste):

if element == mål:

return i

return -1

```

Binær søgning O(log n): kræver sorteret liste — del og hersk.

```python

def binær_søg(sorteret, mål):

lav, høj = 0, len(sorteret) - 1

while lav <= høj:

midt = (lav + høj) // 2

if sorteret[midt] == mål:

return midt

elif sorteret[midt] < mål:

lav = midt + 1

else:

høj = midt - 1

return -1

```

Sorteringsalgoritmer:

Boble-sortering O(n²) — simple men langsom:

```python

def boble_sorter(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]

```

Hurtigsortering (Quicksort) O(n log n) — mest praktisk:

```python

def quicksort(liste):

if len(liste) <= 1: return liste

pivot = liste[len(liste)//2]

venstre = [x for x in liste if x < pivot]

midt = [x for x in liste if x == pivot]

højre = [x for x in liste if x > pivot]

return quicksort(venstre) + midt + quicksort(højre)

```

Pythons sorted() bruger Timsort (O(n log n), stabil).

Læringsmål

• Implementere lineær og binær søgning
• Implementere boble-sortering og forklare dens begrænsninger
• Forklare og implementere Quicksort
• Vælge korrekt søge/sorterings-algoritme baseret på kontekst

Sådan kan du arbejde med emnet

• Implementér bubble sort eller en lignende simpel sorteringsalgoritme i kode
• Forklar hvordan binær søgning virker, og hvorfor det kræver en sorteret liste
• Sammenlign tidsforbruget ved lineær søgning og binær søgning for en stor liste

Træningsforslag

• Mål tidsforskel mellem lineær og binær søgning på 10.000 elementer
• Implementer alle 3 sorteringsalgoritmer og sammenlign køretider
• Løs Leetcode Binary Search (let) og Two Sum (let)