WikiDer > Quicksort

Animations-Schnellsortierung

Schnelle Sorte ist ein rekursivSortieralgorithmus erfunden von Tony Hoare. Zu dieser Zeit arbeitete er an einem Projekt im Zusammenhang mit der Computerübersetzung. Dazu war es notwendig, kurze russische Sätze schnell und effizient zu sortieren. Das allgemeine Funktionsprinzip von Quicksort wird manchmal kurz beschrieben als teilen und erobern.

Arbeitsprinzip

Der Zweck von Quicksort besteht darin, eine Folge von unsortierten Zahlen sortiert zurückzugeben. Dies geschieht in 4 Schritten.

1. Wenn die Zeile ein oder keine Elemente enthält. STOPP
2. Wählen Sie ein beliebiges Element in der Zeile aus. Dieses in der Abbildung blau markierte Element wird als Pivot oder Pivot bezeichnet.
3. Ordnen Sie die Zeile so um, dass alle Elemente mit einem Wert kleiner oder gleich dem Pivot links vom Pivot enden und alle Elemente mit einem Wert größer als der Pivot rechts vom Pivot enden. Dieser Schritt wird als Partitionierung bezeichnet.
4. Sortieren Sie die linke und rechte Teilreihe. (Durch Quicksort.)

• 

  Zum Aufteilen

• 

  Nach der Partitionierung

Folgende Punkte sind hier erwähnenswert: In Schritt 2 wird ein zufälliges Element ausgewählt. Jede Wahl der Spindel führt zu einem Arbeitsalgorithmus. Die willkürliche Auswahl der Spindel führt praktisch zu den besten Ergebnissen, hat aber einige theoretische Nachteile. Dies erschwert die Analyse des Algorithmus. Außerdem erfüllt ein Algorithmus mit einem beliebigen Schritt nicht die strengeren Definitionen von a Algorithmus.In Schritt 3 wird nicht angegeben, wie dieser Schritt ausgeführt wird. Dies variiert in verschiedenen Implementierungen. Der genaue Ablauf dieses Schrittes wird unter der Überschrift Partitionierung besprochen.In Schritt 4 ruft sich der Algorithmus selbst auf. Quicksort ist daher ein rekursiver Algorithmus.

Partitionierung

Es gibt mehrere Möglichkeiten, die Zeile zu partitionieren. Hier wird die Methode von Nico Lomuto diskutiert.

Darstellung der Unterzeilen

Um diesen Algorithmus zu verstehen, muss man wissen, dass er mit 3 aufeinanderfolgenden Teilsequenzen arbeitet.

• Die Unterzeile, die kleinere oder gleiche Elemente enthält. Besetzt die Positionen [0,i-1]
• Die Unterzeile, die größere Elemente enthält. Deckt [i,j-1] ab
• Die Unterzeile mit allen noch nicht verglichenen Elementen. Deckt [y,n-1]

Die Grundidee des Algorithmus ist nun einfach. Bringen Sie die Spindel zuerst in die letzte Position. Nehmen Sie das erste Element aus der Unterzeile der noch nicht verglichenen Elemente und vergleichen Sie es mit dem Pivot. Platzieren Sie dieses Element hinter der Unterzeile, in der es platziert werden soll. Passen Sie dann die Grenzen der Unterzeilen an.

Eine Animation des Lomuto-Algorithmus

Der formale Algorithmus wird nun

1. Platzieren Sie die Spindel an der Rückseite der Reihe.
2. solange j
3. Wenn Element an Position j kleiner oder gleich Spindel ist.
   1. Vertausche die i- und j-Stellen.
   2. Angenommen i=i 1
4. Angenommen j = j 1;

Nach Ausführung des Algorithmus befindet sich die Spindel in Position i und die Zeile wird partitioniert.

Unten ist eine grafische Darstellung.

Zeitkomplexität

Rund um die Komplexität Um Quicksort zu berechnen, basiert die Argumentation auf der Anzahl der Gleichungen. Die erwartete Anzahl der benötigten Gleichungen ist in der Reihenfolge Ö(n*log(n)). In dem Informationstheorie es ist bewiesen, dass ${Anzeigestil O(n*log(n))}$ ist hierfür eine untere Grenze.^[1] Beachten Sie, dass Zählen sortieren und Radix sortieren kann schneller arbeiten. Diese Algorithmen benötigen hingegen Informationen über den Bereich der zu sortierenden Werte. Darüber hinaus scheint es experimentell zu sein, dass Quicksort bei kleineren Zeilen schlecht abschneidet.

Worst-Case-Szenario

Wenn es maximal oder Minimum (aus der unsortierten Unterzeile) systematisch als Pivot-Element gewählt wird, kann die Leistung von Quicksort drastisch sinken. In diesem Fall ist die Zeitkomplexität ${Anzeigestil O(n^{2})}$ Beträge. Im Allgemeinen ist die Wahrscheinlichkeit, dass dies zufällig geschieht, äußerst gering. Aber wenn die Reihe strukturiert ist, wird diese Chance real. Nehmen wir nun an, dass der Algorithmus so implementiert ist, dass er immer das erste Element in der Zeile als Pivot wählt. Wenn dieses Programm eine bereits sortierte Liste sortieren muss, nimmt es systematisch das kleinste Element als Pivot. Um dies zu vermeiden, wird die Spindel in der Praxis oft willkürlich gewählt. Eine andere Lösung besteht darin, den Median des ersten, letzten und mittleren Elements zu wählen.^[2]

Einige einzigartige Werte

Der zweite Fall ist das Sortieren einer Zeile mit wenigen eindeutigen Werten. Dies ist beispielsweise der Fall, wenn Sie eine Liste von Personen nach Geschlecht sortieren möchten. Der Sortieralgorithmus schnell-3 die eng mit quicksort verwandt ist, löst dieses Problem elegant.

Fast sortierte Reihe

Wenn Quicksort (mit zufällig ausgewählter Spindel) eine fast sortierte Reihe sortieren muss, hat der Algorithmus eine Zeitkomplexität von ${Anzeigestil O(n*log(n))}$ haben. Dies ist niedriger als bei flexiblen Sortieralgorithmen wie Sortieren durch Einfügen oder Blase sortieren wo die Zeitkomplexität ${Anzeigestil O(n^{2})}$ beläuft sich auf. Quicksort ist also kein flexibler Algorithmus.

Wenn jedoch das erste oder letzte Element als Pivot gewählt wird, ist die Komplexität ${Anzeigestil O(n^{2})}$ Beträge. Da (fast) alle Werte immer hinter oder vor dem Pivot stehen, werden keine (wenn vollständig sortiert) oder fast keine (wenn fast sortiert) Unterzeilen erstellt und der Algorithmus wird suboptimal arbeiten.^[3]

Raumkomplexität

Das Raumkomplexität von Quicksort ist ${Anzeigestil O(log(n))}$. Dies ist leicht zu erkennen. Schließlich müssen log(n)-Funktionsaufrufe gespeichert werden. Beachten Sie, dass das Speichern der Zeile O(n) nicht berücksichtigt wird. Es wird nur der zusätzlich belegte Speicher berechnet. Wenn man einen naiven Partitionierungsalgorithmus wählt, einen, der die Zeile kopiert. Dann ist die Raumkomplexität O(n).

Optimierungen bei quicksort

Schnell-3

Quicksort funktioniert schlecht, wenn nur wenige eindeutige Werte vorhanden sind. Der Quick-3-Algorithmus löst dies auf elegante Weise. Dies geschieht durch Partitionierung mit 3 Unterzeilen anstelle von 2. Eine Unterzeile, die alle Elemente enthält, deren Wert kleiner ist als der des Pivots. Eine Unterzeile, die alle Elemente enthält, deren Wert dem des Pivots entspricht. Und eine Unterzeile mit allen größeren Werten.^[4] Es wird daher empfohlen, immer quick-3 zu verwenden.

Kleine Scharreihen

Es stellt sich heraus, dass Quicksort in kleinen Reihen schlecht abschneidet. Deshalb entscheiden sich die Leute manchmal dafür Sortieren durch Einfügen für kleine Reihen zu verwenden. Der Wert, für den dies zu tun ist, wird dann experimentell bestimmt.

Nur Zahlen

Wenn Sie nur Zahlen sortieren müssen und mehr Speicher verwendet werden kann, ist es besser zu wählen Zählen sortieren.

Allgemeine Verwendung

Unabhängig von der Eingabe erreicht der randomisierte Quicksort eine Zeitkomplexität von ${Anzeigestil O(n*log(n))}$. Was gleich der absoluten unteren Schranke ist. Andere Algorithmen können diese Barriere jedoch in einigen Fällen durchbrechen. Daraus schließen wir, dass Quicksort (oder besser Quick-3) ein idealer Algorithmus ist, wenn keine Informationen über die zu sortierenden Daten vorliegen. Dies zeigt sich daran, dass Quicksort in die Standardbibliotheken von C und C .

Beispiel in C#

ÖffentlichkeitLeereSchnelle Sorte(int[]Aufführen){Sortieren(Aufführen,0,Aufführen.Länge-1);// Tisch, links und rechts passieren}/*Schnelle Sorte*/PrivatgeländeLeereSortieren(int[]Aufführen,intLinks,intRecht){intl=Links;intR=Recht;intmittleresElement=Aufführen[(LinksRecht)/2];tun{während(Aufführen[l]<mittleresElement){l  ;}während(mittleresElement<Aufführen[R]){R--;}wenn(l<=R){intlinkes Element=Aufführen[l];Aufführen[l]=Aufführen[R];Aufführen[R]=linkesElement;l  ;R--;}}während(l<R);wenn(Links<R){Sortieren(Aufführen,Links,R);}wenn(l<Recht){Sortieren(Aufführen,l,Recht);}}/*Sortieren*/

Beispiel in Scala

Eine Implementierung des Quicksort-Algorithmus in Reichweite (anschaulich, da die Sortierung auch in der Scala Standard Library API aufgerufen werden kann):

// Vorlage für generische Sortierung, wenn sie sortierbar ist "[A <% Ordered[A]]"defschnelle Sorte[ein<%Bestellt[ein]](xs:aufführen[ein]):aufführen[ein]=xsSpiel{FallNull=>xs// leere Liste, leere Liste zurückgebenFallDrehpunkt::list_ohne_header=>// aufgelöste Liste mit den Fragmenten Kopf und Schwanzlist_ohne_headerPartition(_<Drehpunkt)// die Liste in zwei Listen aufteilenSpiel{Fall(unten,über)=>schnelle Sorte(unten)(Drehpunkt::schnelle Sorte(über))}}

Beispiel im Prolog

% Version mit Rekursionqsort([],[]).qsort([Drehpunkt|Sich ausruhen],Sortiert):-Teilt(Drehpunkt,Sich ausruhen,kleiner,Größer),qsort(kleiner,KS),qsort(Größer,GS),anhängen(KS,[Drehpunkt|gs],Sortiert).% Version mit Tail-Rekursion (ein akkumulierender Parameter)qsort(Aufführen,Sortiert):-qsort(Aufführen,[],Sortiert).qsort([],l,l).qsort([Drehpunkt|R],Acc,Sortiert):-Teilt(Drehpunkt,R,kleiner,Größer],qsort(Größer,Acc,NeuAcc),qsort(kleiner,[Drehpunkt|NeuAcc],Sortiert).Teilt(Drehpunkt,[],[],[]).Teilt(Drehpunkt,[X|R],kleiner,Größer):-Drehpunkt>X,kleiner=[X|RestK],Teilt(Drehpunkt,R,RestK,Größer).Teilt(Drehpunkt,[X|R],kleiner,Größer):-Drehpunkt=<X,Größer=[X|RuheG],Teilt(Drehpunkt,R,kleiner,RuheG).

Beispiel in Python3

defSchnelle Sorte(Array,niedrigster Wert,Länge):wennniedrigster Wert<Länge:q=Partition(Array,niedrigster Wert,Länge)Schnelle Sorte(Array,niedrigster Wert,q-1)Schnelle Sorte(Array,q1,Länge)RückkehrArraydefPartition(Array,niedrigster Wert,Länge):Drehpunkt=Array[Länge]ich=niedrigster Wert-1temp=0zumjaimReichweite(niedrigster Wert,Länge):wennArray[ja]<=Drehpunkt:ich =1temp=Array[ja]Array[ja]=Array[ich]Array[ich]=temptemp=Array[ich1]Array[ich1]=Array[Länge]Array[Länge]=tempRückkehr(ich1)

Verweise