www.wikidata.de-de.nina.az
Quicksort englisch quick schnell und to sort sortieren ist ein schneller rekursiver nicht stabiler Sortieralgorithmus der nach dem Prinzip Teile und herrsche arbeitet Er wurde ca 1960 von C Antony R Hoare in seiner Grundform entwickelt 1 und seitdem von vielen Forschern verbessert Der Algorithmus hat den Vorteil dass er uber eine sehr kurze innere Schleife verfugt was die Ausfuhrungsgeschwindigkeit stark erhoht und dass er abgesehen von dem fur die Rekursion zusatzlichen benotigten Platz auf dem Aufruf Stack ohne zusatzlichen Speicherplatz auskommt Eine zufallige Permutation von Integerwerten wird mit Quicksort sortiert Die blauen Linien zeigen den Wert des rot markierten Pivotelements im jeweiligen Rekursionsschritt Im Durchschnitt fuhrt der Quicksort Algorithmus O n log n displaystyle mathcal O n cdot log n Vergleiche durch Im schlechtesten Fall werden O n 2 displaystyle mathcal O n 2 Vergleiche durchgefuhrt was aber in der Praxis sehr selten vorkommt 2 Die Zahlen von 1 bis n in zufalliger Reihenfolge werden mit Quicksort sortiert Inhaltsverzeichnis 1 Prinzip 2 Pseudocode 3 Beispiele 3 1 teile links rechts 3 2 Vollstandiges Beispiel fur alphabetische Sortierung 4 Kenngrossen 4 1 Laufzeit 4 2 Speicherplatz 5 Varianten 5 1 QuickSort fur verkettete Listen 5 2 Iteratives Quicksort 5 3 QuickSort in funktionalen Sprachen 5 4 Parallel Quicksort 6 Literatur 7 Weblinks 8 EinzelnachweisePrinzip BearbeitenZunachst wird die zu sortierende Liste in zwei Teillisten linke und rechte Teilliste getrennt Dazu wahlt Quicksort ein sogenanntes Pivotelement aus der Liste aus Alle Elemente die kleiner als das Pivotelement sind kommen in die linke Teilliste und alle die grosser sind in die rechte Teilliste Die Elemente die gleich dem Pivotelement sind konnen sich beliebig auf die Teillisten verteilen Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste Anschliessend muss man also noch jede Teilliste in sich sortieren um die Sortierung zu vollenden Dazu wird der Quicksort Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgefuhrt Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort Algorithmus angewandt und so weiter Diese Selbstaufrufe werden als Rekursion bezeichnet Wenn eine Teilliste der Lange eins oder null auftritt so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion Die Positionen der Elemente die gleich dem Pivotelement sind hangen vom verwendeten Teilungsalgorithmus ab Sie konnen sich beliebig auf die Teillisten verteilen Da sich die Reihenfolge von gleichwertigen Elementen zueinander andern kann ist Quicksort im Allgemeinen nicht stabil Das Verfahren muss sicherstellen dass jede der Teillisten mindestens um eins kurzer ist als die Gesamtliste Dann endet die Rekursion garantiert nach endlich vielen Schritten Das kann z B dadurch erreicht werden dass das ursprunglich als Pivot gewahlte Element auf einen Platz zwischen den Teillisten gesetzt wird und somit zu keiner Teilliste gehort Pseudocode BearbeitenDie Implementierung der Teilung erfolgt als In place Algorithmus Die Elemente werden nicht in zusatzlichen Speicher kopiert sondern nur innerhalb der Liste vertauscht Dafur wird ein Verfahren verwendet das als Teilen oder auch Partitionieren bezeichnet wird Danach sind die beiden Teillisten gleich in der richtigen Position Sobald die Teillisten in sich sortiert wurden ist die Sortierung der Gesamtliste beendet Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus wobei daten die zu sortierende Liste mit n Elementen ist Bei jedem Aufruf von quicksort gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten Beim ersten Aufruf oberste Rekursionsebene ist links 0 und rechts n 1 Die ubergebene Liste wird dabei rekursiv immer weiter geteilt bis sie nur noch einen Wert enthalt funktion quicksort links rechts falls links lt rechts dann teiler teile links rechts quicksort links teiler 1 quicksort teiler 1 rechts ende ende Die folgende Implementierung der Funktion teile teilt das Feld so dass sich das Pivotelement an seiner endgultigen Position befindet und alle kleineren Elemente davor stehen wahrend alle grosseren danach kommen funktion teile links rechts i links Starte mit j links vom Pivotelement j rechts 1 pivot daten rechts wiederhole solange i lt j solange i an j nicht vorbeigelaufen ist Suche von links ein Element welches grosser als das Pivotelement ist wiederhole solange i lt j und daten i lt pivot i i 1 ende Suche von rechts ein Element welches kleiner oder gleich dem Pivotelement ist wiederhole solange j gt i und daten j gt pivot j j 1 ende falls daten i gt daten j dann tausche daten i mit daten j ende ende Tausche Pivotelement daten rechts mit neuer endgultiger Position daten i und gib die neue Position des Pivotelements zuruck beende Durchlauf falls daten i gt pivot dann tausche daten i mit daten rechts sonst i rechts ende antworte i ende Nach der Wahl des Pivotelementes wird zunachst ein Element vom Anfang der Liste beginnend gesucht Index i welches grosser als das Pivotelement ist Entsprechend wird vom Ende der Liste beginnend ein Element kleiner als das Pivotelement gesucht Index j Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Teilliste Dann werden die beiden Suchvorgange von den erreichten Positionen fortgesetzt bis sich die untere und obere Suche treffen dort ist die Grenze zwischen den beiden Teillisten Beispiele Bearbeitenteile links rechts Bearbeiten Die Buchstabenfolge einbeispiel soll alphabetisch sortiert werden Ausgangssituation nach Initialisierung von i und j das Element rechts l ist das Pivotelement e i n b e i s p i e l i j Nach der ersten Suche in den inneren Schleifen hat i auf einem Element gt l und j auf einem Element lt l gehalten e i n b e i s p i e l i j Nach dem Tauschen der Elemente bei i und j e i e b e i s p i n l i j Nach der nachsten Suche und tauschen e i e b e i i p s n l i j Nach einer weiteren Suche sind die Indizes aneinander vorbeigelaufen e i e b e i i p s n l j i Nach dem Tauschen von i und Pivot bezeichnet i die Trennstelle der Teillisten Bei i steht das Pivot Element links davon sind nur Elemente Pivot und rechts nur solche gt Pivot e i e b e i i l s n p i Vollstandiges Beispiel fur alphabetische Sortierung Bearbeiten In diesem Beispiel soll der Quicksortalgorithmus die Buchstabenfolge Quicksort sortieren Zunachst wird das rechte Element P gt als Pivotelement definiert Dann laufen die Zahler g fur grosser von links nach rechts und k fur kleiner von rechts nach links los Quicksort g kP bis g auf ein Element trifft welches grosser als das Pivotelement ist und bis k auf ein Element trifft welches kleiner oder gleich dem Pivotelement ist Quicksort g kP Diese beiden gefundenen Elemente r und u werden dann im folgenden Schritt getauscht Qricksout g kP Im folgenden Schritt laufen die Indizes k und g in der gleichen Richtung wie gehabt weiter und suchen Elemente die bei k kleiner als oder gleich dem Pivotelement und bei g grosser als das Pivotelement sind Qricksout kgP Jetzt sind k und g aneinander vorbeigelaufen Dieses Ereignis ist eine Abbruchbedingung Jetzt wird das Pivotelement mit dem durch g indizierten Element getauscht Qricksotu kPg Jetzt treffen folgende zwei Aussagen zu Links des Pivotelements sind alle Elemente kleiner oder gleich dem Pivotelement Rechts des Pivotelements sind alle Elemente grosser oder gleich dem Pivotelement links rechts Qrickso t u k P g Das Pivotelement teilt nun die Datenmenge an der Stelle des Pivotelements in zwei Halften Links und Rechts Nun muss der Algorithmus den linken und den rechten Teil auf die gleiche Weise wie im Vorangehenden schon geschehen weiterbehandeln Hierdurch ergibt sich nun die Rekursion Der rechte Teil Der Buchstabe u ist nur ein einzelnes Element und ist somit per Definition sortiert Also wird nun der linke Teil behandelt Das rechte Element ist wieder das Pivotelement und die Zahler werden passend gesetzt Qrickso t u g kP Das Q ist grosser als o und das k ist kleiner als das o Qrickso t u g k P Also werden das Q und das k vertauscht kricQso t u g k P Indizes g und k laufen weiter kricQso t u g k P Das r und das c werden getauscht kcirQso t u g k P Im folgenden Schritt sind die Indizes wieder aneinander vorbeigelaufen kcirQso t u kg P und das Pivotelement Buchstabe o wird mit dem grosseren Element Buchstabe r getauscht kcioQsr t u kP g Nun ergibt sich erneut ein linker und ein rechter Teil links rechts kci o Qsr t u k P g Zunachst wird der linke Teil behandelt kci o Qsr t u g kP g kP cki o Qsr t u gkP g kP Buchstabe c und k werden getauscht cki o Qsr t u kgP g kP Indizes sind aneinander vorbeigelaufen und das Element des Index g wird mit dem des Index P vertauscht cik o Qsr t u kPg g kP Der jetzt entstandene neue linke und rechte Teil besteht nun nur noch aus einem einzelnen Element und gilt als sortiert cik o Qsr t u kgP Im ehemals rechten Teil Buchstaben Qsr laufen die Indizes direkt aneinander vorbei und das Element bei g wird mit dem Pivotelement getauscht cik o Qrs t u kPg Damit sind alle Zeichen sortiert cik o Qrs t u Ergebnis cikoQrstuKenngrossen BearbeitenLaufzeit Bearbeiten Die Laufzeit des Algorithmus hangt im Wesentlichen von der Wahl des Pivotelementes ab Im Worst Case schlechtesten Fall wird das Pivotelement stets so gewahlt dass es das grosste oder das kleinste Element der Liste ist Dies ist etwa der Fall wenn als Pivotelement stets das Element am Ende der Liste gewahlt wird und die zu sortierende Liste bereits sortiert vorliegt Die zu untersuchende Liste wird dann in jedem Rekursionsschritt nur um eins kleiner und die Zeitkomplexitat wird beschrieben durch O n 2 displaystyle mathcal O n 2 nbsp Die Anzahl der Vergleiche ist in diesem Fall n n 1 2 1 n 2 2 n 2 1 displaystyle tfrac n cdot left n 1 right 2 1 tfrac n 2 2 tfrac n 2 1 nbsp Im Best Case besten Fall wird das Pivotelement stets so gewahlt dass die beiden entstehenden Teillisten etwa gleich gross sind In diesem Fall gilt fur die asymptotische Laufzeit des Algorithmus O n log n displaystyle mathcal O n cdot log n nbsp Diese Zeitkomplexitat gilt ebenso fur den Average Case durchschnittlichen Fall Die Lange der jeweils langeren Teilliste beim rekursiven Aufruf ist namlich im Schnitt 2 n i n 2 n 1 i 3 4 n 2 4 displaystyle textstyle frac 2 n sum limits i frac n 2 n 1 i frac 3 4 n frac 2 4 nbsp und die Tiefe der Rekursion damit in O log n displaystyle mathcal O log n nbsp Im Average Case ist die Anzahl der Vergleiche etwa 2 log 2 n 1 log 2 n 1 39 n 1 log 2 n displaystyle 2 cdot log 2 cdot n 1 cdot log 2 n approx 1 39 cdot n 1 cdot log 2 n nbsp 3 Fur die Wahl des Pivotelementes sind in der Literatur verschiedene Ansatze beschrieben worden Die Wahrscheinlichkeit des Eintreffens des Worst Case ist bei diesen unterschiedlich gross Ein moglicher Ansatz ist es immer das erste das letzte oder das mittlere Element der Liste zu wahlen Dieser naive Ansatz ist aber relativ ineffizient Eine andere Moglichkeit ist es den Median dieser drei Elemente zu bestimmen und als Pivotelement zu verwenden Ein anderer Ansatz ist als Pivotelement ein zufalliges Element auszuwahlen Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit dass das Pivotelement in jedem Teilungsschritt so gewahlt wird dass sich die Worst Case Laufzeit ergibt extrem gering Man kann davon ausgehen dass er praktisch nie auftritt Es gibt Algorithmen beispielsweise Heapsort deren Laufzeiten auch im Worst Case durch O n log n displaystyle mathcal O n cdot log n nbsp beschrankt sind In der Praxis wird aber trotzdem Quicksort eingesetzt da angenommen wird dass bei Quicksort der Worst Case nur sehr selten auftritt und im mittleren Fall schneller als Heapsort ist da die innerste Schleife von Quicksort nur einige wenige sehr einfache Operationen enthalt Dies ist jedoch noch Forschungsgegenstand und einige Analysen und Simulationen sehen Heapsortvarianten vorne sowohl aus informationstheoretischen Uberlegungen wie Implementierungsbetrachtungen 4 5 Heute ist Quicksort fur ein breites Spektrum von praktischen Anwendungen der bevorzugte Sortieralgorithmus weil er schnell ist und sofern Rekursion zur Verfugung steht einfach zu implementieren ist In vielen Standardbibliotheken ist er bereits vorhanden Mittlerweile steht jedoch mit Introsort auch eine Alternative zur Verfugung die bei vergleichbarer mittlerer Laufzeit auch fur den Worst Case eine obere Schranke von O n log n displaystyle mathcal O n cdot log n nbsp garantiert Verwendet man fur die Wahl des Pivotelements den Median of medians Algorithmus welcher den Median eines Arrays in O n displaystyle mathcal O n nbsp bestimmt so kann insgesamt eine Laufzeit von O n log n displaystyle mathcal O n cdot log n nbsp fur den schlechtesten Fall von Quicksort garantiert werden Speicherplatz Bearbeiten Quicksort ist ein in Place Verfahren Es vertauscht zwar die Elemente der zu sortierenden Liste nur innerhalb der Liste und kopiert sie nicht in zusatzlichen Speicherplatz benotigt dafur jedoch fur jede Rekursionsebene zusatzlichen Platz auf dem Stack Wie bei der Laufzeit hangt auch der Speicherverbrauch von der Wahl des Pivotelements und der Art der vorliegenden Daten ab Im gunstigsten und durchschnittlichen Fall bei einer Rekursionstiefe in O log n displaystyle mathcal O log n nbsp wird auch nur eine Stapelgrosse von O log n displaystyle mathcal O log n nbsp benotigt Im ungunstigsten Fall ist die Anzahl der Rekursionen nur durch die Listenlange n displaystyle n nbsp beschrankt was einen Stapel der Grosse O n displaystyle mathcal O n nbsp erfordert Dies kann bei langen Listen zu einem Stapeluberlauf fuhren Es gibt vielfaltige Modifikationen des Algorithmus um dieses Problem zu losen oder zumindest die Wahrscheinlichkeit seines Auftretens zu vermindern 6 Endrekursionsbeseitigung siehe nachfolgender Pseudocode eine ausgewogenere Wahl des Pivotelements z B Median von Drei Wahl eines zufalligen Pivotelements wodurch systematische Probleme vermieden werden die sich sonst durch bestimmte Vorsortierungen der Elemente im Zusammenspiel mit der Methode der Pivotwahl ergeben konnen Vermeidung von Teillisten mit weniger als zwei Elementen ergibt wenn auch das Pivotelement aus den Teillisten genommen wird die maximale Rekursionstiefe n 3 displaystyle n 3 nbsp Der folgende Pseudocode ersetzt die Endrekursion Sortierung der zweiten Teilliste durch eine Iteration derart dass die kurzere Teilliste rekursiv sortiert wird die langere wird iterativ so lange erneut geteilt und die jeweils kurzere Teilliste rekursiv sortiert bis der verbleibende Rest leer ist Die Rekursionstiefe ist dann nicht grosser als log n displaystyle log n nbsp funktion quicksort links rechts solange rechts gt links wiederhole teiler teile links rechts falls rechts teiler gt teiler links quicksort links teiler 1 kleinere Teilliste rekursiv links teiler 1 und grossere iterativ sortieren sonst quicksort teiler 1 rechts rechts teiler 1 ende ende ende Eine weitere Moglichkeit den in n displaystyle n nbsp linearen zusatzlichen Speicherplatz zu vermeiden besteht darin dass man zuerst die kleinere der beiden Teilfolgen rekursiv sortiert die andere wird danach sortiert aber ebenfalls rekursiv Somit bleibt die Anzahl der noch nicht sortierten Teilfolgen durch O log n displaystyle mathcal O log n nbsp beschrankt Fur jede noch nicht sortierte Teilfolge werden zwei Indexgrenzen gespeichert die jeweils O log n displaystyle mathcal O log n nbsp zusatzlichen Speicherplatz benotigen Insgesamt benotigt Quicksort mit dieser Variante O log 2 n displaystyle mathcal O log 2 n nbsp zusatzlichen Speicherplatz Varianten BearbeitenQuickSort fur verkettete Listen Bearbeiten Bei nachfolgend dargestellter QuickSort Variante fur verkettete Listen wird als Pivotelement das jeweils erste der zu teilenden Folge gewahlt Ein Zeiger Zeiger2 wird soweit vorgeschoben bis er auf ein Element trifft das kleiner als das Pivot ist Die Elemente uber die Zeiger2 hinweggegangen ist sind demzufolge grosser oder gleich dem Pivot Ein Tausch des ersten dieser grosseren Elemente mit dem bei Zeiger2 sorgt also dafur dass die betreffenden Elemente im richtigen Teilabschnitt landen Zeiger1 markiert das aktuelle Ende des Teilabschnitts der Elemente die kleiner als das Pivot sind Wenn Zeiger2 am rechten Rand der zu teilenden Folge angelangt ist wird abschliessend das Pivotelement an die richtige Position zwischen den Teilfolgen getauscht Links Rechts sind hier Zeiger QuickSort Links Rechts falls Links lt gt Rechts dann Initialisierung der lokalen Zeiger Zeiger0 wird nur als Vorganger von Zeiger1 benotigt Zeiger0 Links Zeiger1 Links Zeiger2 Links Pivot Links Zahl wiederhole Zeiger2 Zeiger2 Nachfolger falls Zeiger2 Zahl lt Pivot dann Zeiger0 Zeiger1 Zeiger1 Zeiger1 Nachfolger tausche Zeiger1 Zeiger2 solange bis Zeiger2 Rechts tausche Links Zeiger1 falls Zeiger1 lt gt Rechts dann Zeiger1 Zeiger1 Nachfolger QuickSort Links Zeiger0 QuickSort Zeiger1 Rechts ende Der Nachteil dieses Verfahrens liegt darin dass eine weitgehend sortierte Folge oder viele gleichartige Schlusselwerte zu einem Worst Case ahnlichen Verhalten fuhren Daher wahlt man fur verkettete Listen gern Sortieralgorithmen wie etwa Mergesort die auch im Worst Case eine Zeitkomplexitat von O n log n displaystyle mathcal O n log n nbsp besitzen Andere dynamische Datenstrukturen wie balancierte Baume z B B Baume AVL Baume verteilen die Kosten des Sortierens auf die Einfugeoperationen so dass nachtragliches Sortieren nicht notwendig ist Iteratives Quicksort Bearbeiten Quicksort kann auch nicht rekursiv mit Hilfe eines kleinen Stack oder Array implementiert werden Hier eine einfache Variante mit zufalliger Auswahl des Pivotelements funktion quicksort iterativ links rechts zufall random zufalliger Startwert wiederhole aussere Schleife solange links lt rechts wiederhole pivot daten random links rechts Auswahl eines zufalligen Elements das zwischen links und rechts liegt push rechts rechten Teil spater sortieren mitte links wiederhole innere Schleife teile Feld solange daten mitte lt pivot wiederhole suche falsch einsortiertes Element von links mitte mitte 1 ende solange daten rechts gt pivot wiederhole suche falsch einsortiertes Element von rechts rechts rechts 1 ende falls mitte gt rechts dann Abbruch innere Schleife tausche daten mitte mit daten rechts ende Feld geteilt linken Teil weitersortieren ende falls stapel leer dann Abbruch aussere Schleife noch ein rechter Teil ubrig links rechts 1 pop rechts jetzt rechten Teil sortieren ende ende Die Anweisung push legt dabei ein Element auf den Stack wo es mit pop wieder geholt wird Die zufallige Wahl des Pivotelements sorgt dabei mit hoher Wahrscheinlichkeit fur einen Average Case Die Grosse des notigen Stapelspeichers ist dabei mit ausreichender Sicherheit kleiner als 2 log2 n Falls ein begrenzter Stapel trotzdem uberlauft so kann zum Sortieren des noch verbleibenden Teils einfach von vorne begonnen werden Die Effizienz von Quicksort liegt darin dass es Elemente aus grosser Distanz miteinander vertauscht Je kurzer die zu sortierende Liste wird desto ineffizienter arbeitet Quicksort da es sich einer Komplexitat von O n 2 displaystyle mathcal O n 2 nbsp nahert Die von Quicksort in Teillisten zerlegte Liste hat jedoch die Eigenschaft dass der Abstand zwischen einem Element und seiner sortierten Position nach oben beschrankt ist Eine solche Liste sortiert Insertionsort in linearer Zeit so dass haufig in der Implementierung unterhalb einer definierten Teillistenlange der Quicksort abgebrochen wird um mit Insertionsort weiter zu sortieren QuickSort in funktionalen Sprachen Bearbeiten In funktionalen Sprachen wie Haskell oder Erlang lasst sich QuickSort aufgrund machtigerer Listenverarbeitung sehr einfach implementieren quicksort Ord a gt a gt a quicksort quicksort e es quicksort x x lt es x lt e e quicksort x x lt es x gt e Dabei ist der Verkettungsoperator fur Listen das Pattern e es isoliert das erste Element der Liste und x x lt es x lt e ergibt alle Elemente der Liste es die kleiner sind als das Pivotelement e Parallel Quicksort Bearbeiten Hauptartikel Parallel Quicksort Wenn mehrere Prozessoren kerne zur Verfugung stehen ist es auch moglich Quicksort zu parallelisieren Damit sind unter Umstanden bessere Laufzeiten erreichbar Literatur BearbeitenRobert Sedgewick Algorithmen Pearson Studium 2002 ISBN 3 8273 7032 9 Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Introduction to Algorithms 2 Auflage MIT Press Cambridge MA 2001 ISBN 0 262 03293 7 Standardwerk zu Algorithmen Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Algorithmen Eine Einfuhrung 2 korr Auflage Oldenbourg Munchen Wien 2007 ISBN 978 3 486 58262 8 englisch Introduction to algorithms Ubersetzt von Karen Lippert Micaela Krieger Hauwede Weblinks BearbeitenKompakte Erklarung des Quicksort Algorithmus Vollstandiger Quicksort Artikel linux related de JavaScript Demonstration vieler Sortieralgorithmen auch des Quicksort Algorithmus englisch Vorlesung zum Thema Quicksort MIT englisch Einzelnachweise Bearbeiten C A R Hoare Quicksort In The Computer Journal Band 5 1 1962 S 10 15 doi 10 1093 comjnl 5 1 10 Steven S Skiena The Algorithm Design Manual Springer 2011 ISBN 978 1 84800 069 8 S 129 google com abgerufen am 18 Juli 2013 Performanceof Quicksort PDF University of Illinois System Department of Mathematics Statistics and Computer Science Paul Hsieh Sorting revisited In azillionmonkeys com 2004 abgerufen am 26 April 2010 englisch David MacKay Heapsort Quicksort and Entropy Nicht mehr online verfugbar www aims ac za mackay 1 Dezember 2005 archiviert vom Original am 7 Juni 2007 abgerufen am 26 April 2010 englisch Ellis Horowitz Sartaj Sahni Susan Anderson Freed Grundlagen von Datenstrukturen in C 1 Auflage International Thomson Publishing 1994 ISBN 3 929821 00 1 S 342 Abgerufen von https de wikipedia org w index php title Quicksort amp oldid 236932398