Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

37.2.1 Quicksort

37.2.1 Quicksort

Fangen wir als erstes mit Quicksort an, da jenes noch relativ einfach zu verstehen ist und auch das Gebräuchlichste ist. Das Grundprinzip ist, dass ich meine Liste Teile und in die eine alle kleinen Elemente packe und in die andere alle großen. Somit hab ich hab ich schon einmal grob sortiert. Man kann sich das wie ein Sieb vorstellen. Anschließend wird dieses Prinzip auf die 2 Listen angewandt, was zur Folge hat, dass die Liste mit kleinen Elementen in eine Liste mit winzigen und in eine mit relativ kleinen Elementen geteilt wird, wohingegen die Liste der großen in mittelgroße und ganz große geteilt wird und so weiter und sofort. Dies wird so lange gemacht, bis man nur noch Teillisten hat, die nur noch ein Element besitzen. Wie wird das aber im einzelnen realisiert? Hier wieder eine Grafik.

Veranschaulichung des Quicksort Sortierverfahrens

Zuerst wird ein s.g. Pivotelement bestimmt, was üblicherweise immer das Letzte ist, also im ersten Schritt die 4. Jetzt wird "gleichzeitig" von vorne, nach größeren Elementen gesucht und von hinten, nach kleineren. Sobald jeweils ein größeres und ein kleineres gefunden wird, werden sie vertauscht. Dies wird so lange gemacht, bis sich die zwei Suchpositionen überlappen. Jetzt ist die Liste also für die Teilung vorbereitet und es wird nur noch das Element an der Stelle der Überlappung mit dem Pivotelement getauscht, also die 7 mit der 4. Nun wird Quicksort für die Liste [3, 1, 2] und die Liste [5, 6, 7] aufgerufen.

Beim ersten Unteraufruf von Quicksort, wird die 2 pivotisiert und alles was davor steht wieder für eine Teilung vorbereitet. Dies hat zur Folge, dass die 1 mit der 3 getauscht werden und da sich die Suchpositionen dann überlappen, wird die 3 mit der 2 getauscht. Jetzt wird wieder Quicksort für die Listen [1] und [3] aufgerufen, was zur Folge hat, dass hier abgebrochen wird, da Listen mit einem Element sortiert sind. Der Linke Teil der gesamten Liste ist jetzt sortiert, da Pivotelemente immer an der richtigen Stelle stehen und somit den sortierten Bereich darstellen (auch wenn er zerpflückt ist). Jetzt wird der Spaß ja noch für die Liste [5, 6, 7] durchgeführt und hier sieht man auch gleich sehr schön den Nachteil von Quicksort. Da die Liste eigentlich schon sortiert ist, wird kein Element mehr gefunden, welches größer ist als das Pivotelement, was zur Folge hat, dass Quicksort für die Liste [5, 6] aufgerufen wird, wo wieder das selbe Problem auftritt.

Im aller schlimmsten Fall braucht Quicksort also auch quadratische Laufzeit in seiner Standardimplementierung. Allerdings hat man schon einige Ideen entwickelt, um diesen Entartungsfall einer vor sortierten Liste, zu begegnen. Ein Ansatz ist das Prinzip der verbesserten Pivotisierung. Hier wird nicht einfach das letzte Element genommen. Außerdem kann man für kleine Teillisten auch Insertionsort benutzen. Ich hab ja gesagt, dass die Algorithmen bei relativ wenigen Elementen keinen spürbaren zeitlichen Unterschied machen. Zudem nimmt man Insertionsort, weil es genau mit diesem "bösen"> Fall, besonders gut, nämlich linear, umgehen kann.

Allerdings hat Quicksort trotzdem noch ein großen Pferdefuß. Mit jedem Durchlauf werden ja rekursiv, zwei weitere Quicksortfunktionen aufgerufen, welche wiederum jeweils zwei aufrufen. Dies hat zur Folge, dass es nicht lange dauert, bis man einen Stackoverflow verursacht, da ein Rechner nicht mit unendlich vielen Aufrufen von Subroutinen umgehen kann. Man kann dem zwar entgegen kommen, in dem man wie erwähnt für kleine Teillisten Insertionsort benutzt und somit keine weiteren Aufrufe hat, allerdings hilft dies bei spätestens Zehnmillionen Elementen, auch nichts mehr. Aus diesem Grund hat man s.g. iterative Quicksortalgorithmen "erfunden", welche statt Aufrufe von Subroutinen, sich entsprechende Teilbereiche in Hilfslisten speichert. Man verlagert dadurch das Problem lediglich vom Stack auf den Heap. Nun ist der Heap um einiges größer, weshalb man mehr Luft hat, aber auch hier gibt es Hardware bedingte Grenzen und auf den Heap kann man nicht ganz so schnell zugreifen, da Indirektionen durch Pointer hinzukommen.

Im Anhang finden Sie einmal das einfache Quicksort und zudem das optimierte Verfahren mit der verbesserten Pivotisierung und Insertionsort. Auf den iterativen Algorithmus habe ich verzichtet. Aber die Umbauten dafür wären nicht so Problematisch. Sie bräuchten wie gesagt lediglich eine Liste, welche Positionen halten kann und eine große Schleife, welche so lange arbeitet, bis nichts mehr in der Liste steht. Statt dann zwei mal die Quicksortfunktion mit den Positionen der Teilbereiche aufzurufen, speichern Sie diese Teilbereiche einfach in der Liste (vorausgesetzt der Teilbereich ist größer als eins) und fertig.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012