Sorteringsalgoritmer — quicksort, merge sort, heapsort

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Sorteringsalgoritmer — quicksort, merge sort, heapsort

Sorteringsalgoritmer = grundlæggende computerscience. Klassiske comparison-baserede (kan ikke gå hurtigere end O(n log n) i worst case):

1.

Quicksort — divide & conquer. Vælg pivot, partitionér så alle < pivot er til venstre, > til højre. Rekursiv på sub-arrays.

Tidskompleksitet: gennemsnit O(n log n), worst case O(n²) (allerede sorteret data + dårlig pivot).

Plads: O(log n) for stack. In-place (modificerer original array).

Dominant i praksis — Python's Timsort, C's qsort, JavaScript's V8.

2.

Merge sort (John von Neumann 1945) — divide & conquer. Splitt array i 2 halvdele, sortér rekursivt, MERGE de sorterede.

Tidskompleksitet: ALTID O(n log n) — stable.

Plads: O(n) — IKKE in-place. Stabil (bevarer relativ orden af lige-keys). Bruges i ekstern sortering (data > RAM).

3.

Heapsort — bygger max-heap, ekstrahér roden iterativt.

Tidskompleksitet: O(n log n).

Plads: O(1) in-place. Ikke stabil. Mindre cache-friendly end quicksort.

Simple algoritmer (O(n²) — ikke til store data): (4)

Bubble sort — sammenlign nabopars, swap. Pædagogisk, ineffektiv. (5)

Selection sort — find min, swap. (6)

Insertion sort — én ad gangen, indsæt på rette sted. EFFEKTIV for SMÅ array (n < 50) eller næsten-sorteret. Bruges som "base case" i hybrid-algoritmer (Timsort, Introsort).

Specielle algoritmer (linear time, ikke comparison-baseret): (7)

Counting sort — kun for heltal i kendt range. O(n+k). (8)

Radix sort — sor

Læringsmål

• Redegøre for virkemåden af quicksort, merge sort og heapsort
• Sammenligne algoritmernes tidskompleksitet
• Implementere en af sorteringsalgoritmerne

Sådan kan du arbejde med emnet

• Implementér merge sort i Python og spor, hvad der sker med et 8-elements array trin for trin
• Forklar, hvad der er quicksorts bedste, gennemsnitlige og værste tilfældes kompleksitet
• Sammenlign quicksort, merge sort og heapsort med hensyn til stabilitet og pladsbehov

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.