# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/algorithmen/README.txt]

SORTIERALGORITHMEN
==================

Stand: 2026-01-28

UEBERBLICK
----------
Sortierung ist eines der grundlegendsten Probleme der Informatik. Effizientes Sortieren ist Basis fuer Suche, Datenbanken und Datenanalyse.

EINFACHE VERFAHREN (O(n^2))
---------------------------
Diese Algorithmen sind leicht zu verstehen, aber fuer grosse Datenmengen ineffizient.

### Bubble Sort
Durchlaeuft die Liste und tauscht benachbarte Elemente, wenn sie falsch stehen. "Blasen" (grosse Elemente) steigen auf.
- Vorteil: Sehr einfach zu implementieren.
- Nachteil: Extrem langsam.

### Selection Sort
Sucht das kleinste Element und tauscht es an den Anfang. Dann das naechstkleinste fuer Pos 2, etc.
- Vorteil: Wenige Schreiboperationen (Swaps).
- Nachteil: Immer O(n^2), auch wenn schon sortiert.

### Insertion Sort
Nimmt Elemente, eines nach dem anderen, und fuegt sie an der richtigen Stelle in den bereits sortierten Teil ein (wie Spielkarten sortieren).
- Vorteil: Sehr schnell bei kleinen n oder fast sortierten Listen.

EFFIZIENTE VERFAHREN (O(n log n))
---------------------------------

### Merge Sort (Divide & Conquer)
Teilt die Liste rekursiv in Haelften, sortiert diese und mischt ("merges") sie dann geordnet wieder zusammen.
- Vorteil: Garantiert O(n log n), stabil (behaelt Reihenfolge gleicher Elemente).
- Nachteil: Braucht O(n) zusaetzlichen Speicher.

### Quick Sort
Waehlt ein "Pivot"-Element. Teilt Liste in "kleiner als Pivot" und "groesser als Pivot". Rekursiver Aufruf.
- Vorteil: Meist der schnellste in der Praxis (in-place).
- Nachteil: Worst Case O(n^2) (bei schlechter Pivot-Wahl).

### Heap Sort
Nutzt einen Binary Heap (Datenstruktur), um immer das Maximum zu extrahieren.
- Vorteil: O(n log n) und in-place.
- Nachteil: Nicht stabil, langsame CPU-Cache Performance.

SPEZIELLE VERFAHREN
-------------------
Fuer Zahlen oder Strings mit fester Laenge gibt es Verfahren, die schneller als O(n log n) sind.
- **Counting Sort:** Zaehlt Vorkommen von Elementen (nur fuer kleine Integer-Bereiche).
- **Radix Sort:** Sortiert Ziffer fuer Ziffer (Einer, Zehner, Hunderter...).

PYTHON SORT()
-------------
Python nutzt `Timsort`, eine Hybrid-Kombination aus Merge Sort und Insertion Sort. Es ist stabil und extrem effizient fuer reale Daten.

SIEHE AUCH
----------
wiki/informatik/algorithmen/komplexitaet.txt
wiki/python/funktionen/ (sorted)
