Zur MathePrisma-Startseite
Zur Modul-Startseite  


Sortierverfahren (Quicksort 3)
 

 
 


































Quicksort ist am schnellsten
 

Für die  Aufwandsanalyse orientieren wir uns am  C-Programm.

 Schlüsselvergleiche: Die Berechnung der Schlüsselvergleiche ist wegen der rekursiven Aufrufe komplizierter.
Deswegen seien nur die Ergebnisse angegeben.

Der schlechteste Fall tritt auf, wenn die Folge absteigend sortiert ist.



Im Mittel werden nicht wesentlich mehr Schlüsselvergleiche benötigt als im besten Fall.



 Umspeicherungen:

Da die Anzahl der Umspeicherungen höchstens so groß ist wie die Anzahl der Schlüsselvergleiche, folgt:


Quicksort erreicht damit im Mittel den geringsten Aufwand unter allen betrachteten Verfahren. Man kann sogar zeigen, dass es wesentlich schnellere Verfahren gar nicht geben kann.

 
Seite 14/17