Sorteringsalgoritmer — quicksort, merge sort, heapsort

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Sorteringsalgoritmer

Merge sort — del og kombiner, O(n log n) garanteret:

```python

def merge_sort(liste):

if len(liste) <= 1:

return liste

midt = len(liste) // 2

venstre = merge_sort(liste[:midt])

højre = merge_sort(liste[midt:])

return merge(venstre, højre)

```

Quicksort — vælg pivot, del i to, O(n log n) gennemsnit, O(n²) worst case:

```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)

```

Heapsort — bruger heap-datastruktur, O(n log n), in-place.

Python: sorted() og list.sort() bruger Timsort (hybrid merge sort + insertion sort) — O(n log n) guaranteed.

Sammenligning: Merge sort er stabil og forudsigelig. Quicksort er hurtigst i praksis. Heapsort er O(1) ekstra hukommelse.

Læringsmål

• Implementere merge sort og quicksort rekursivt
• Forklare forskellen i kompleksitet og stabilitet
• Vælge passende sorteringsalgoritme til konteksten
• Bruge Pythons built-in sort med key-funktioner

Sådan kan du arbejde med emnet

• Sortér listen [5, 2, 9, 1, 5, 6] trin for trin med quicksort
• Forklar hvordan merge sort deler og fletter listen
• Sammenlign tidskompleksiteten for quicksort, merge sort og heapsort i bedste og værste tilfælde

Træningsforslag

• Implementér merge sort og mål køretid mod Pythons sort
• Visualisér quicksort trin-for-trin med print-statements
• Sorter en liste af dictionaries efter flere kriterier med key=