Hvordan vælger du mellem sorteringsalgoritmer?

Question

Accepted Answer

Valg af sorteringsalgoritme afhænger af nogle få egenskaber: **tidsompleksitet**, **stabilitet**, **hukommelsesforbrug på stedet** og dataenes natur. Ingen enkelt algoritme vinder alle steder.

## Vigtige egenskaber

- **Stabil:** elementer med samme værdi bevarer deres oprindelige relative rækkefølge (nødvendig for sortering med flere nøgler).
- **På stedet:** bruger O(1) eller O(log n) ekstra hukommelse.
- **Adaptiv:** hurtigere på næsten sorterede data.

## Sammenligning

| Algoritme | Gennemsnit | Værste tilfælde | Stabil | På stedet |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Ja | Ja |
| Merge | O(n log n) | O(n log n) | Ja | Nej |
| Quick | O(n log n) | O(n²) | Nej | Ja |
| Heap | O(n log n) | O(n log n) | Nej | Ja |

## Vejledning

- **Små / næsten sorterede** -> insertion sort.
- **Skal have stabilitet eller garanteret O(n log n)** -> merge sort.
- **Generelt hurtig in-memory, gennemsnitshastighed betyder noget** -> quicksort (randomiseret pivot).
- **Garanteret grænse + tight hukommelse** -> heap sort.

```python
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority)   # stable Timsort in Python
```

## Almindelige fejl

Implementer ikke din egen sorteringsalgoritme, medmindre du har en specifik grund — biblioteksalgoritmer (Timsort, introsort) er velafprøvede hybrider.

## Hvorfor det betyder noget

At matche sorteringsalgoritmen med data og krav undgår både spildt tid og subtile fejl (som at miste stabilitet).

At forstå afvejningerne forklarer, hvorfor standardbiblioteker valgte hybrider som Timsort og introsort.

Dette komparative skøn — ikke memorering af én algoritme — er det, som rigtig teknik og interviews værdsætter.

Algoritme	Gennemsnit	Værste tilfælde	Stabil	På stedet
Insertion	O(n²)	O(n²)	Ja	Ja
Merge	O(n log n)	O(n log n)	Ja	Nej
Quick	O(n log n)	O(n²)	Nej	Ja
Heap	O(n log n)	O(n log n)	Nej	Ja