Kapitel 7. Sortier-Algorithmen
Sortierproblem: Gegeben Folge von Datensätzen (items) s1, s2, ... sn
Jedes si besitzt Schlüssel ki (meist vom Typ integer).
Gesucht: Permutation p, so daß kp(1)? kp(2) ? ... ? kp(n)
Interne Sortierverfahren: alle Datensätze im Hauptspeicher, sonst Nutzung des Externspeichers
Anzahl der Schlüsselvergleiche C (Comparisons) und Anzahl der Zuweisungen von Datensätzen M (Moves).
C min, C max, C mit jeweils
M min, M max, M mit minimale, maximale, mittlere Anzahl