Quick-Sort

Quick-Sort

Quick-Sort, sehr schneller Algorithmus. Laufzeit

. Die zu sortierenden Daten werden in zwei möglichst gleich große Gruppen aufgeteilt, so daß alle Elemente der ersten Gruppe kleiner sind als alle Elemente der zweiten Gruppe. Nun wird rekursiv jede dieser Gruppen für sich sortiert. Werden die sortierten Gruppen wieder aneinander gehängt, so sind alle Daten sortiert.

 
    PROCEDURE quicksort(anfang,ende: integer;
    VAR a: sortfeld); 
    VAR i,j,x: integer; 
    BEGIN
       i:=anfang; j:=ende; 
       x:=a[(anfang+ende) DIV 2]; (* trennt die Gruppen *) 
       REPEAT 
           WHILE a[i]<x DO i:=i+1; 
            (* grosses Element suchen *)
           WHILE a[j]>x DO j:=j-1;  
            (* kleines Element suchen *)
           IF i<=j THEN BEGIN   
               swap(a[i],a[j]); 
               i:=i+1; j:=j-1; }
           END;
       UNTIL i>j;
       IF anfang<j THEN quicksort(anfang,j,a);
       IF i<ende THEN quicksort(i,ende,a);
    END;