Das Sortierverfahren- QUICKSORT

Dieses Verfahren beruht auf der wiederholten Teilung des Datenfeldes in 2 neue Felder,
wobei die Daten der Felder bezüglich eines Vergleichselements sortiert werden.
Das Verfahren endet, wenn nur noch einelementige Felder vorhanden sind.
Diese einelementigen Felder werden schließlich nur noch zum sortierten Datenfeld
zusammengesetzt.

Struktogramm :

N Zahlen werden in ein Feld eingelesen. Am Anfang ist links=1 und rechts=N.

Struktogramm

Es sind nun 2 Teilfelder entstanden.          
                             1.Teilfeld: zahlen[links..j]       2.Teilfeld: zahlen[i..rechts]
Auf diese Teilfelder wird der Algorithmus erneut angewendet.

Beispiel:

                                 4       9      8      7     1

 

 

 

 

 

 

Dieser Algorithmus ist sehr schnell und damit für sehr große Datenmengen geeignet.
Der Aufwand berechnet sich näherungsweise durch die Formel

                                               Aufwandsformel

Ermitteln Sie:

Aufwand(10) 
Aufwand(100) 
Aufwand(1000)
Aufwand(10000) 

 

Die 3 Diagramme machen den Unterschied zum für sehr große Datenmengen uneffektiveren
Bubble-Sort grafisch deutlich.

Aufwand

 

Quicksort mit manueller Zahleneingabe      Quelltext
Quicksort für größere Zahlenmengen          Quelltext