Quicksort
Quicksort ist einer der weitverbreitetsten Sortieralgorithmen. Vorteile sind das gute Laufzeitverhalten und die effiziente Speichernutzung. Mit steigender Elementzahl steigt der Berechnungsaufwand nur in der Ordnung O(n*logn). Der größte Nachteil des Algorithmus ist die schwierige Implementierung, da diese exakt durchgeführt werden muss. Kleine Fehler im Programmcode können unsinnige Ergebnisse produzieren. Wegen der erhöhten Komplexität soll das Funktionsprinzip hier detailliert erklärt werden. Dazu wird der Algorithmus in drei Teilen betrachtet:
Teil 1:
Der Input der Funktion sei ein Vektor, dessen Elemente sortiert werden müssen:
a = [5 7 10 2 1 9 8 6]
g k p
Beim ersten Aufruf des Quicksort-Algorithmus werden drei Variablen, die als Referenz zu drei Elementen des Vektors dienen, erzeugt. Diese werden g (für 'größer'), k (für 'kleiner'), und p (für 'Pivot') genannt. Zusätzlich werden die zwei Variablen links und rechts definiert, auf die später noch eingegangen wird. Die Pivot-Variable hat den Wert 8, für die achte Stelle des Vektors. g hat den Wert 1 für die erste Stelle des Vektors und k den Wert 7 für die zweitletzte Stelle des Vektors. Das zugehörige Pivot-Element hat somit den Wert 6.
g dient als Laufparameter und wird so lange erhöht, bis das Element des Vektors an der Stelle g größer als das Pivot-Element ist. Das erste Element ist 5 und somit niedriger als das Pivot-Element 6. Entsprechend wird g um eins erhöht und erhält den Wert 2.
a = [5 7 10 2 1 9 8 6]
g k p
Das zweite Element 7 ist größer als das Pivot-Element 6. Da nun ein größeres Element von links gefunden wurde, muss ein kleineres von rechts gefunden werden. Das wird durch den zweiten Laufparameter k erreicht. Das k-te Element des Vektors hat den Wert 8 und ist größer als das Pivot-Element. Deshalb wird der Wert 1 von k abgezogen. Nun verweist es auf die sechste Stelle des Vektors mit dem Wert 9. Auch dieser ist nicht kleiner als das Pivot-Element. Erst bei der fünften Stelle erhält es mit 1 ein niedrigeres Element.
a = [5 7 10 2 1 9 8 6]
g k p
Da nun beide Elemente gefunden wurden, werden die Elemente im Vektor vertauscht:
a = [5 1 10 2 7 9 8 6]
g k p
Danach wird der Wert von g weiter erhöht, bis das entsprechende Element im Vektor größer als das Pivot-Element ist. Das ist zufällig genau das nächste Element. Also muss wieder k so lange reduziert werden, bis das entsprechende Element im Vektor kleiner ist als das Pivot-Element. Dies trifft bereits auf das nächste Element nach links zu.
a = [5 1 10 2 7 9 8 6]
g k p
Entsprechend werden wieder die Elemente an den Stellen g und k vertauscht:
a = [5 1 2 10 7 9 8 6]
g k p
Nun wird mit dieser Prozedur fortgefahren. Das nächste Element für die Laufvariable g, das größte als das Pivot-Element 6 ist, ist 10. Der nächste Wert für die Laufvariable k, der kleiner als der Pivot-Element ist, ist 2:
a = [5 1 2 10 7 9 8 6]
k g p
Nun ist die Variable g weiter rechts (bzw. hat einen höheren Wert) als die Variable k. Das ist das Signal, den ersten Teil des Algorithmus zu beenden und den zweiten Teil einzuleiten:
Teil 2:
Im zweiten Teil werden nun das Pivot-Element und das g-Element vertauscht:
a = [5 1 2 6 7 9 8 10]
k p g
Die folgende Feststellung kann nun getroffen werden: Links vom Pivot-Element sind nur noch Werte, die kleiner sind als das Pivot-Element selbst. Rechts davon sind nur Werte, die größer sind. Nun kann das Feld am Pivot-Element in zwei Felder aufgteilt werden. Nun kann die linke Seite für sich und die rechte Seite für sich auf die gleiche Weise sortiert werden. Dazu bietet es sich kann, den gleichen Algorithmus nochmal zu verwenden. Hier kommen die anfangs erwähnten Variablen links und rechts zum Einsatz. Es macht keinen Sinn, den ganzen Vektor nochmal zu sortieren, also werden die linke und die rechte Schranke übergeben, die zu Beginn 1 und 8 betrugen. Damit wird das divide-and-conquer Prinzip klar.
Teil 3:
Der erste Aufruf des Algorithmus könnte so ausgesehen haben:
a = [5 7 10 2 1 9 8 6];
a_sortiert = quickSort(1,length(a),a)
Nun müssen aber die linke und die rechte Seite für sich ebenfalls sortiert werden. Entsprechend bietet sich ein rekursiver Aufbau an. Das heißt, der Algorithmus ruft sich selber auf, jedoch diesmal mit anderen Schranken. Für die linke Seite könnte der Aufruf wie folgt aussehen:rueckgabe = quickSort(links,p-1,a)
Für die rechte Seite entsprechend:
rueckgabe = quickSort(p+1,rechts,a)
Damit wird der zu sortierende Vektor in immer kleinere Teilvektoren aufgeteilt, die dann erneut sortiert und aufgeteilt werden.
Hinweis: In diesem Beispiel wurde als Pivot-Element immer die rechte Schranke gewählt, weil dadurch der Algorithmus relativ anschaulich erklärt werden kann. Statt der rechten Schranke kann jedoch auch ein anderer Wert verwendet werden, was bei einer geschickten Auswahl zu einem deutlich effektiveren Algorithmus führen kann.
Ablauf:
Wie in der theoretischen Einführung dargestellt, arbeitet der Algorithmus mit einer Zerlegung des Vektors in zwei Teilvektoren. Anschließend wird der Sortieralgorithmus für den beiden Teilvektoren ausgeführt. Hier der Algorithmus nochmal im Pseudocode:
Pseudocode:
function rueckgabe = Quicksort(links,rechts,Feld)
g = links
k = rechts-1
p = rechts
solange g<k
% Erhöhe g solange, bis ein Wert größer gleich dem
% Pivot-Element gefunden wurde ohne die rechte Seite zu erreichen
solange Feld(g)<=Feld(p) und g<rechts
erhöhe g um 1
ende
% analog für k
solange Feld(k)>=Feld(p) und k>links
senke k um 1
ende
% wurden beide inneren Schleifen durchlaufen, sind die Werte gefunden
% oder g hat einen höheren Wert als k
Wenn g<k
Vertausche im Vektor die Werte an der Stelle g und Stelle k
ende
ende
% Wenn das Programm hier ankommt, steht g weiter rechts als k
Wenn Feld(p)<Feld(g)
Vertausche im Feld die Werte an der Stelle g und p
p = g %neue Pivotstelle für weitere Funktionen ist an der Stelle g
ende
% sicher gehen, dass Schranken nicht nur ein Element umschließen
Wenn p-1>links
Feld = Quicksort(links,p-1,Feld) %Wende gleichen Algorithmus links des neuen Pivotelements an
ende
% sicher gehen, dass Schranken nicht nur ein Element umschließen
Wenn p+1<rechts
Feld = Quicksort(p+1,rechts,Feld) %Wende gleichen Algorithmus rechts des neuen Pivotelements an
ende
rueckgabe = Feld
ende
Lösungsvorschlag:
Quicksort
function Feld = Quicksort(links,rechts,Feld)
% Conquer - Teil
g = links;
k = rechts-1;
p = rechts;
while (g<k)
while(Feld(g)<=Feld(p) && g<rechts)
g=g+1;
end
while(Feld(k)>=Feld(p) && k>links)
k=k-1;
end
if (g<k)
zw=Feld(g);
Feld(g)=Feld(k);
Feld(k)=zw;
end
end
if (Feld(p)<Feld(g))
zw=Feld(g);
Feld(g)=Feld(p);
Feld(p)=zw;
p=g;
end
% Divide - Teil
if (p-1>links)
Feld = Quicksort(links,p-1,Feld);
end
if (p+1<rechts)
Feld = Quicksort(p+1,rechts,Feld);
end
end