Wahl der Leser
Populäre Artikel
Hoare-Methode – Schnellsortierung. Rekursiver Quicksort-Algorithmus in aufsteigender Reihenfolge. Dreipartitionssortierung
Es handelt sich um eine verbesserte Sortiermethode, die auf dem Austauschprinzip basiert. Die Blasensortierung ist der ineffizienteste aller direkten Sortieralgorithmen. Der verbesserte Algorithmus ist jedoch die bekannteste Methode zum Sortieren von Arrays. Es hat so brillante Eigenschaften, dass sein Erfinder Charles Hoare es Quick Sort nannte.
Um die größtmögliche Effizienz zu erreichen, ist es wünschenswert, Elemente über große Entfernungen auszutauschen. Im Array wird ein Element ausgewählt, das als Auflösen bezeichnet wird. Es wird dann an der Stelle im Array platziert, wo es sein soll, nachdem alle Elemente geordnet wurden. Bei der Suche nach einem geeigneten Ort für das Auflösungselement werden die Elemente neu angeordnet, sodass sich links davon Elemente befinden, die kleiner als das Auflösungselement sind, und rechts davon größere (vorausgesetzt, das Array ist aufsteigend sortiert). Befehl).
Dadurch wird das Array in zwei Teile geteilt:
- unsortierte Elemente links vom Auflösungselement;
- unsortierte Elemente rechts vom Auflösungselement.
Um diese beiden kleineren Subarrays zu sortieren, ruft sich der Algorithmus rekursiv auf.
Wenn Sie mehr als ein Element sortieren müssen, müssen Sie Folgendes tun
- Wählen Sie ein auflösendes Element im Array aus.
- Ordnen Sie das Array neu an und platzieren Sie das Element an seiner endgültigen Stelle.
- Sortieren Sie rekursiv die Elemente links vom Resolver.
- Sortieren Sie rekursiv die Elemente rechts vom Resolver.
Das Schlüsselelement von Quicksort ist Neuordnungsalgorithmus.
Schauen wir uns die Sortierung am Beispiel eines Arrays an:
10, 4, 2, 14, 67, 2, 11, 33, 1, 15.
Um den Neuordnungsalgorithmus zu implementieren, verwenden wir den linken Zeiger auf das Element ganz links im Array. Der Zeiger bewegt sich nach rechts, bis die Elemente, auf die er zeigt, unter der Auflösung bleiben. Wir platzieren den rechten Zeiger auf dem Element ganz rechts im Array und bewegen ihn nach links, bis die Elemente, auf die er zeigt, größer als die Auflösung bleiben.
Das Element ganz links sei ein Pivot-Resolver. Setzen Sie den linken Zeiger auf das darauf folgende Element. richtig - bis zum letzten. Der Algorithmus muss die korrekte Position von Element 10 ermitteln und dabei die Plätze falsch platzierter Elemente vertauschen.
Die Bewegung der Zeiger stoppt, sobald Elemente angetroffen werden, deren Reihenfolge im Verhältnis zum auflösenden Element falsch ist.
Der linke Zeiger bewegt sich, bis er ein Element größer als 10 anzeigt; nach rechts bewegt sich, bis ein Element kleiner als 10 angezeigt wird.
Diese Elemente werden vertauscht und die Bewegung der Zeiger wird fortgesetzt.
Der Vorgang wird fortgesetzt, bis rechts links von links liegt.
Dadurch wird die korrekte Position des Auflösungselements bestimmt.
Das auflösende Element wird mit dem Element vertauscht, auf das right zeigt. 
Das auflösende Element befindet sich an der richtigen Stelle: Elemente links davon haben kleinere Werte; rechts - große. Der Algorithmus wird rekursiv aufgerufen, um die Subarrays links vom Resolver und rechts davon zu sortieren.
Implementierung des Schnellsortierungsalgorithmus in C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#enthalten
#enthalten
#define GRÖSSE 20
// Schnelle Sortierfunktion
void quickSort(int *Zahlen, int links, int rechts)
{
int Pivot; // Berechtigungselement
int l_hold = left; //linker Rand
int r_hold = rechts; // rechter Rand
Pivot = Zahlen;
während (links< right) // bis die Grenzen schließen
{
while ((Zahlen >= Pivot) && (links< right))
Rechts--; // den rechten Rand verschieben, bis das Element größer ist
if (links != rechts)
{
Zahlen = Zahlen; // Element an die zulässige Position verschieben
links++; // den linken Rand nach rechts verschieben
}
während ((Zahlen<= pivot) && (left < right))
links++; // den linken Rand verschieben, bis das Element kleiner ist
if (links != rechts) // wenn die Grenzen nicht geschlossen sind
{
Zahlen = Zahlen; // Verschiebe das Element an seinen Platz
Rechts--; // den rechten Rand nach rechts verschieben
}
}
Zahlen = Pivot; // Setzen Sie das aktivierende Element ein
Drehpunkt = links;
left = l_hold;
rechts = r_hold;
wenn (links< pivot) // Sortierung für den linken und rechten Teil des Arrays rekursiv aufrufen
quickSort(Zahlen, links, Pivot - 1);
if (rechts > Pivot)
quickSort(Zahlen, Pivot + 1, rechts);
}
int main()
{
int a;
// Das Array mit Zufallszahlen füllen
für (int i = 0; i
// Array-Elemente vor dem Sortieren ausgeben
für (int i = 0; i
printf("\n" );
quickSort(a, 0, SIZE-1); // Sortierfunktion aufrufen
// Array-Elemente nach dem Sortieren ausgeben
für (int i = 0; i
printf("\n" );
getchar();
0 zurückgeben;
}
Ausführungsergebnis
Ziel: den Schnellsortierungsalgorithmus und seine Modifikationen studieren.
In dieser Lektion beschäftigen wir uns mit dem Quicksort-Algorithmus, der wahrscheinlich am häufigsten verwendet wird als jeder andere. Die Grundlage des Algorithmus wurde 1960 (C.A.R.Hoare) entwickelt und seitdem von vielen Menschen sorgfältig untersucht. Quicksort ist besonders beliebt, weil es einfach zu implementieren ist; Es handelt sich um einen ziemlich guten Allzweckalgorithmus, der in vielen Situationen gut funktioniert und gleichzeitig weniger Ressourcen verbraucht als andere Algorithmen.
Die Hauptvorteile dieses Algorithmus bestehen darin, dass er punktweise arbeitet (nur einen kleinen zusätzlichen Stapel verwendet), im Durchschnitt nur etwa N log N Operationen zum Sortieren von N Elementen erfordert und eine extrem kurze innere Schleife hat. Die Nachteile des Algorithmus bestehen darin, dass er rekursiv ist (die Implementierung ist sehr schwierig, wenn keine Rekursion verfügbar ist), im schlimmsten Fall N2-Operationen erfordert und außerdem sehr „fragil“ ist: ein kleiner Fehler in der Implementierung, der dazu führen kann leicht unbemerkt bleiben, kann dazu führen, dass der Algorithmus bei manchen Dateien sehr schlecht funktioniert.
Die Leistung von Quicksort wurde gut untersucht. Der Algorithmus wurde einer mathematischen Analyse unterzogen, sodass es präzise mathematische Formeln zu Fragen seiner Leistung gibt. Die Ergebnisse der Analyse wurden wiederholt empirisch überprüft und der Algorithmus so verfeinert, dass er für eine Vielzahl von Sortieraufgaben am besten geeignet war. All dies macht es lohnenswert, den Algorithmus genauer zu untersuchen, um herauszufinden, wie er am effektivsten umgesetzt werden kann. Ähnliche Implementierungen funktionieren auch für andere Algorithmen, aber in Quicksort können wir sie bedenkenlos verwenden, da die Leistung gut untersucht wurde.
Die Verbesserung des Quicksort-Algorithmus ist eine große Versuchung: Ein schnellerer Sortieralgorithmus ist eine Art „Mausefalle“ für Programmierer. Fast von dem Moment an, als Oia?a seinen Algorithmus erstmals veröffentlichte, tauchten in der Literatur „verbesserte“ Versionen dieses Algorithmus auf. Viele Ideen wurden ausprobiert und analysiert, aber es ist immer noch sehr leicht, sich täuschen zu lassen, da der Algorithmus so gut ausbalanciert ist, dass eine Verbesserung in einem Teil davon zu einer größeren Verschlechterung in einem anderen Teil führen kann. Wir werden drei Modifikationen dieses Algorithmus, die ihm eine deutliche Verbesserung verleihen, im Detail untersuchen.
Eine gut abgestimmte Version von Quicksort wird wahrscheinlich viel schneller laufen als jeder andere Algorithmus. Es sei jedoch noch einmal daran erinnert, dass der Algorithmus sehr fragil ist und jede Änderung an ihm zu unerwünschten und unerwarteten Auswirkungen auf einige Eingabedaten führen kann.
Die Essenz des Algorithmus: Die Anzahl der Operationen zum Ändern der Positionen von Elementen innerhalb eines Arrays wird erheblich reduziert, wenn weit voneinander entfernte Elemente ausgetauscht werden. Dazu wird ein Element x zum Vergleich ausgewählt, das erste Element links gefunden, das nicht kleiner als x ist, und das erste Element rechts gefunden, das nicht größer als x ist. Die gefundenen Elemente werden vertauscht. Nach dem ersten Durchgang befinden sich alle Elemente, die kleiner als x sind, links von x und alle Elemente, die größer als x sind, rechts von x. Machen Sie dasselbe mit den beiden Hälften des Arrays. Setzen Sie die Teilung dieser Hälften fort, bis 1 Element darin verbleibt.
Programm Quitsort; verwendet crt; Konst. N=10; Geben Sie Mas=Array of Integer ein; var a: mas; k:Ganzzahl; function Part(l, r: integer):integer; var v, i, j, b: ganze Zahl; begin V:=a[r]; I:=l-1; j:=r; wiederholen, wiederholen dec(j) bis (a[j]<=v) or (j=i+1);
repeat
inc(i)
until (a[i]>=v) oder (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; bis i>=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; Teil:=i; Ende; Prozedur QuickSort(l, t: integer); var i: Ganzzahl; beginnen, wenn l 60,79, 82, 58, 39, 9, 54, 92, 44, 32
60,79, 82, 58, 39, 9, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
Die „innere Schleife“ von Quicksort besteht lediglich aus der Erhöhung des Zeigers und dem Vergleich der Array-Elemente mit einer festen Zahl. Das macht Quicksort schnell. Eine einfachere innere Schleife kann man sich kaum vorstellen. Auch hier wirken sich die positiven Effekte von Guard Keys aus, da sich eine weitere Prüfung in der inneren Schleife negativ auf die Leistung des Algorithmus auswirken würde. Das fragwürdigste Merkmal des oben genannten Programms ist, dass es bei einfachen Unterdateien sehr ineffektiv ist. Wenn die Datei beispielsweise bereits sortiert ist, werden die Abschnitte entartet und das Programm ruft sich einfach N-mal auf, jedes Mal mit einer um ein Element kleineren Unterdatei. Dies bedeutet, dass nicht nur die Leistung des Programms auf etwa N2/2 sinkt, sondern auch der für seine Ausführung erforderliche Speicherplatz bei etwa N liegt (siehe unten), was inakzeptabel ist. Glücklicherweise gibt es relativ einfache Möglichkeiten, um sicherzustellen, dass ein solcher „Worst Case“-Fall im praktischen Einsatz des Programms nicht eintritt. Wenn die Datei identische Schlüssel enthält, stellen sich zwei weitere zweifelhafte Fragen. Die erste ist, ob beide Zeiger bei Schlüsseln anhalten sollen, die dem Teilungselement entsprechen, oder ob nur einer von ihnen angehalten werden soll und die zweite Frage alle durchgehen soll, oder ob beide Zeiger über sie hinweggehen sollen. Tatsächlich wurde dieses Problem eingehend untersucht und die Ergebnisse zeigten, dass es am besten ist, beide Zeiger zu stoppen. Dadurch können Sie bei Vorhandensein vieler identischer Schlüssel mehr oder weniger ausgeglichene Partitionen aufrechterhalten. Tatsächlich könnte dieses Programm leicht verbessert werden, indem der Scan j beendet wird Leistungsmerkmale von Quick Sort Das Beste, was für den Algorithmus passieren könnte, wäre, wenn jede der Unterdateien in zwei Unterdateien gleicher Größe aufgeteilt würde. Infolgedessen würde die Anzahl der von Quicksort durchgeführten Vergleiche dem Wert des rekursiven Ausdrucks entsprechen CN = 2CN/2+N – der beste Fall. (2CN/2 deckt die Kosten für das Sortieren der beiden resultierenden Unterdateien ab; N ist die Kosten für die Verarbeitung jedes Elements mit dem einen oder anderen Zeiger.) Wir wissen auch, dass der ungefähre Wert dieses Ausdrucks CN = N lg N ist. Obwohl uns diese Situation nicht sehr oft begegnet, entspricht die durchschnittliche Laufzeit des Programms dieser Formel. Die Berücksichtigung der wahrscheinlichen Positionen der einzelnen Abschnitte macht die Berechnungen komplexer, das Endergebnis wird jedoch ähnlich sein. Eigenschaft 1 Quicksort verwendet durchschnittlich 2N ln N Vergleiche. Methoden zur Verbesserung von Quicksort. Die erste Verbesserung des Quicksort-Algorithmus ergibt sich aus der Beobachtung, dass sich das Programm garantiert bei einer großen Anzahl kleiner Unterdateien selbst aufruft. Daher sollten wir die beste Sortiermethode verwenden, wenn wir auf eine kleine Unterdatei stoßen. Ein offensichtlicher Weg, dies zu erreichen, besteht darin, die Prüfung am Anfang der rekursiven Funktion von „if r>l then“ in einen Einfügungs-Sortieraufruf zu ändern (entsprechend geändert, um die Grenzen der zu sortierenden Unterdatei zu berücksichtigen): „if r-l.“<=M then insertion(l, r)." Значение для M не обязано быть "самым-самым" лучшим: алгоритм работает примерно одинаково для M от 5 до 25. Время работы программы при этом снижается примерно на 20% для большинства программ. Bei kleinen Unterdateien (5–25 Elemente) ruft sich die Schnellsortierung viele Male auf (in unserem Beispiel ruft sie sich bei 10 Elementen 15 Mal auf), daher sollten Sie nicht die Schnellsortierung, sondern die Einfügungssortierung verwenden. Prozedur QuickSort (l,t:integer); var i:integer; begin if t-l>m then begin i:=part(l,t); QuickSort(l,i-1); QuickSort(i+1,t); end Else Insert(l,t); Ende; Die zweite Verbesserung des Quicksort-Algorithmus besteht darin, zu versuchen, das beste Teilungselement zu verwenden. Wir haben mehrere Möglichkeiten. Am sichersten wäre es, den schlimmsten Fall zu vermeiden, indem man ein beliebiges Array-Element als Teilungselement wählt. Dann wird die Wahrscheinlichkeit des schlimmsten Falles vernachlässigbar. Dies ist ein einfaches Beispiel für einen „probabilistischen“ Algorithmus, der unabhängig von den Eingabedaten fast immer funktioniert. Zufälligkeit kann ein gutes Werkzeug beim Entwerfen von Algorithmen sein, insbesondere wenn verdächtige Eingaben möglich sind. Eine nützlichere Verbesserung besteht darin, drei Elemente aus der Datei zu nehmen und dann deren Mitte als Trennelement zu verwenden. Wenn die Elemente am Anfang, in der Mitte und am Ende der Datei entnommen werden, können Sie die Verwendung von Schutzelementen vermeiden: Sortieren Sie die drei entnommenen Elemente, tauschen Sie dann das mittlere Element durch a aus und verwenden Sie dann den Divisionsalgorithmus für das Array a. Diese Verbesserung wird als mittlere Dreiteilung bezeichnet. Die Methode der Median-Dreiteilung ist aus drei Gründen nützlich. Erstens ist dadurch die Wahrscheinlichkeit eines Worst-Case-Szenarios deutlich geringer. Damit dieser Algorithmus proportionale N2-Zeit verwendet, müssen zwei der drei genommenen Elemente entweder das kleinste oder das größte sein, und dies muss von Abschnitt zu Abschnitt wiederholt werden. Zweitens macht diese Methode die Notwendigkeit von Schutzelementen überflüssig, da diese Rolle von einem der drei Elemente übernommen wird, die wir vor der Teilung verwendet haben. Drittens verkürzt es tatsächlich die Laufzeit des Algorithmus um etwa 5 %. Prozeduraustausch(i,j:integer); var k:integer; begin k:=a[i]; a[i]:=a[j]; a[j]:=k; Ende; Verfahren Mediana; var i:integer; begin i:=n div 4;(Abb.) wenn a[i]>a dann wenn a[i]>a dann tausche(i,n) sonst tausche(i*3,n) sonst wenn a>a dann tausche (i*2,n); Quicksort(1,n); Ende; Sie können diesen Algorithmus ohne Rekursion mithilfe eines Stapels umschreiben, aber das machen wir hier nicht. Durch die Kombination einer nicht rekursiven Implementierung der mittleren Dreiteilung mit der Beschneidung in kleine Dateien kann die Laufzeit des Algorithmus um 25 bis 30 % verbessert werden. In der heutigen Lektion haben wir uns also mit dem Schnellsortierungsalgorithmus befasst. In der heutigen Lektion beginnen wir, uns mit dem Thema der externen Sortierung zu befassen. Durch die externe Sortierung werden Dateien sortiert, die nicht vollständig in den RAM passen. Die externe Sortierung unterscheidet sich stark von der internen Sortierung. Tatsache ist, dass der Zugriff auf die Datei sequentiell und nicht parallel erfolgt, wie es bei einem Array der Fall war. Daher kann die Datei nur in Blöcken gelesen werden, und dieser Block kann im Speicher sortiert und in die Datei zurückgeschrieben werden. Die grundlegende Fähigkeit, eine Datei effektiv zu sortieren, mit ihren Teilen zu arbeiten und ohne die Grenzen des Teils zu überschreiten, wird durch den Zusammenführungsalgorithmus bereitgestellt. Zusammenführen bezieht sich auf das Zusammenführen von zwei (oder mehr) geordneten Sequenzen zu einer geordneten Sequenz durch Durchlaufen der aktuell verfügbaren Elemente. Das Zusammenführen ist ein viel einfacherer Vorgang als das Sortieren. Wir werden uns zwei Zusammenführungsalgorithmen ansehen: Sequenz a wird in zwei Hälften b und c aufgeteilt. Die Sequenzen b und c werden zusammengeführt, indem einzelne Elemente zu geordneten Paaren kombiniert werden. Die resultierende Sequenz erhält den Namen a, danach werden die Schritte 1 und 2 wiederholt; In diesem Fall verschmelzen geordnete Paare zu geordneten Vierfachen. Die vorherigen Schritte werden wiederholt, wobei Vierer zu Achtern usw. verschmelzen, bis die gesamte Sequenz geordnet ist, weil Die Länge der Sequenzen verdoppelt sich jedes Mal. Beispiel Originalsequenz A = 44 55 12 42 94 18 06 67 1 b = 44 55 12 42 s = 94 18 06 67 a = 44 94" 18 55" 06 12" 42 67 2 b = 44 94" 18 55" s = 06 12" 42 67 a = 06 12 44 94" 18 42 55 67" 3 b = 06 12 44 94" c = 18 42 55 67" a = 06 12 18 42 44 55 67 94 Eine Operation, die den gesamten Datensatz einmal verarbeitet, wird als Phase bezeichnet. Der kleinste Teilprozess, der in seiner Wiederholung den Sortierprozess bildet, wird als Durchlauf oder Stufe bezeichnet. In unserem Beispiel erfolgt die Sortierung in drei Durchgängen. Jeder Durchgang besteht aus einer Split-Phase und einer Merge-Phase. Der Hauptnachteil der Zusammenführungssortierung besteht darin, dass sie die Größe des ursprünglich von den sortierten Daten belegten Speichers verdoppelt. Betrachten wir den von Bose und Nelson vorgeschlagenen rekursiven Zusammenführungsalgorithmus, der keine Speicherreserve erfordert. Es basiert auf einer offensichtlichen Idee: Sie können zwei gleich geordnete Teile zusammenführen, indem Sie ihre Anfangshälften, ihre letzten Hälften zusammenführen und die 2. Hälfte des 1. Ergebnisses mit der 1. Hälfte des 2. Ergebnisses zusammenführen, zum Beispiel: Wenn die Teile nicht gleich sind oder sich nicht genau in zwei Hälften teilen, wird das Verfahren entsprechend angepasst. Ebenso lässt sich die Verschmelzung von „Hälften“ auf die Verschmelzung von „Vierteln“, „Achten“ usw. reduzieren; Es findet eine Rekursion statt. Konst. n=200; Geben Sie tipkl=word; tip = Record kl: tipkl; z:Array von realem Ende; Var A: Anordnung der Spitzen; j:Wort; Prozedur Bose (Var AA; voz:Boolean); Var m,j:word; x:tip; (tip – Art der zu sortierenden Datensätze) A: Array von tip Absolute AA; Prozedur Sli(j,r,m: Wort); (r ist der Abstand zwischen den Anfängen der zusammengeführten Teile und m ist ihre Größe, j ist die kleinste Datensatznummer) Beginn, wenn j+r<=n Then
If m=1 Then
Begin
If voz Xor (A[j].kl < A.kl) Then
Begin
x:=A[j];
A[j]:= A;
A:=x
End
End
Else
Begin
m:=m div 2;
Sli(j,r,m); {Слияние "начал"}
If j+r+m<=n Then
Sli(j+m,r,m); {Слияние "концов"}
Sli(j+m,r-m,m) End {Слияние в центральной части}
End{блока Sli};
Begin
m:=1;
Repeat
j:=1; {Цикл слияния списков равного размера: }
While j+m<=n do
Begin
Sli(j,m,m);
j:=j+m+m
End;
m:=m+m {Удвоение размера списка перед началом нового прохода}
Until m >= n (Ende der Schleife, die den gesamten Zusammenführungsbaum implementiert) End(Bose-Block); BEGIN Randomisieren; Für j:=1 bis n do begin A[j].kl:= Random(65535); Write(A[j].kl:8); Ende; Readln; Bose(A,true); Für j:=1 bis n tun Sie Write(A[j].kl:8); Readln ENDE. Es kombiniert geordnete Teile, die spontan in der ursprünglichen Anordnung entstanden sind; sie können auch eine Folge einer vorangegangenen Datenverarbeitung sein. Es ist nicht notwendig, mit der gleichen Größe der zusammengeführten Teile zu rechnen. Datensätze in nicht absteigender Schlüsselreihenfolge werden zu einer Unterliste verkettet. Die Mindestunterliste ist ein Eintrag. Beispiel: Lassen Sie die Aufnahmeschlüssel vergeben 5 7 8 3 9 4 1 7 6
Auf der Suche nach Unterlisten Die 1., 3., 5. usw. Unterlisten werden zu einer gemeinsamen Liste zusammengefasst, die 2., 4. usw. Unterlisten zu einer anderen. Lassen Sie uns 1 Unterliste von 1 Liste und 1 Unterliste von 2 Listen, 2 Unterlisten von 1 Liste und 2 Unterlisten von 2 Listen usw. zusammenführen. Die folgenden Ketten werden erhalten 3 -> 5 -> 7 -> 8 -> 9 und 1 -> 4 -> 7 Die aus dem Eintrag „6“ bestehende Unterliste hat kein Paar und wird „zwangsweise“ mit der letzten Kette zusammengeführt, die die Form 1 -> 4 -> 6 -> 7 annimmt. Bei unserer geringen Teilnehmerzahl wird die 2. Stufe, in der die beiden Ketten zusammenwachsen, die letzte sein. Im Allgemeinen wird in jeder Phase der Unterliste das Ergebnis der Zusammenführung der ersten Unterlisten 1 und 2 der Liste zum Anfang einer neuen ersten Liste, und das Ergebnis der Zusammenführung der nächsten beiden Unterlisten wird zum Anfang der zweiten Liste. Die nachfolgend gebildeten Unterlisten werden abwechselnd in die 1. und 2. Liste aufgenommen. Für die Softwareimplementierung wird ein Array sp erstellt: Das Element sp[i] ist die Nummer des Datensatzes, der auf das i-te folgt. Der letzte Eintrag einer Unterliste verweist auf den ersten Eintrag einer anderen, und um die Enden der Unterlisten zu unterscheiden, ist dieser Link mit einem Minuszeichen versehen. Wiederholen (Wiederholung der Unterlistenzusammenführungsvorgänge) Wenn A[j].kl< A[i].kl Then {Выбирается меньшая запись}
Begin sp[k]:=j; k:=j; j:=sp[j];
If j<=0 Then {Сцепление с остатком "i"-подсписка}
Begin sp[k]:=i; Repeat m:=i; i:=sp[i] Until i<=0 End
End
Else
Begin sp[k]:=i; k:=i; i:=sp[i];
If i<=0 Then {Сцепление с остатком "j"-подсписка}
Begin sp[k]:=j; Repeat m:=j; j:=sp[j] Until j<=0 End
End;
If j<=0 Then Begin sp[m]:= 0; sp[p]:=-sp[p]; i:=-i;
j:=-j; If j<>0 Dann p:=r; k:=r; r:=m Ende bis j=0; (Eine Nullreferenz (sp[m]:= 0) wird immer am Ende der generierten Unterliste hinzugefügt, da es sich möglicherweise um die letzte handelt. Die Aktion sp[p]:= -sp[p] kennzeichnet das Ende einer zuvor erstellten Unterliste mit einem Minuszeichen. In der heutigen Lektion haben wir uns also mit der Zusammenführung von Algorithmen befasst. Hinweis: In der Praxis wird die sortierte Menge normalerweise nicht in drei, sondern in zwei Teile unterteilt: zum Beispiel „kleiner als die Referenz“ und „gleich und größer“. Im Allgemeinen erweist sich dieser Ansatz als effektiver, da zur Durchführung einer solchen Aufteilung ein Durchlauf durch die sortierte Menge und ein einziger Austausch nur einiger ausgewählter Elemente ausreicht. Quicksort verwendet eine Teile-und-Herrsche-Strategie. Die Schritte des Algorithmus sind: Da in jeder Iteration (auf jeder nächsten Rekursionsebene) die Länge des verarbeiteten Array-Segments um mindestens eins abnimmt, wird der Endzweig der Rekursion immer erreicht und die Verarbeitung wird garantiert abgeschlossen. Interessanterweise hat Hoare diese Methode im Zusammenhang mit der maschinellen Übersetzung entwickelt: Tatsache ist, dass das Wörterbuch zu dieser Zeit auf Magnetband gespeichert war und wenn man alle Wörter im Text anordnet, kann man ihre Übersetzungen in einem Durchgang des Bandes erhalten. Der Algorithmus wurde von Hoare während seines Aufenthalts in der Sowjetunion erfunden, wo er an der Moskauer Universität Computerübersetzung studierte und einen Russisch-Englisch-Sprachführer entwickelte (er soll diesen Algorithmus von russischen Studenten gehört haben). //Algorithmus in Java public static void qSort(int A, int low, int high) ( int i = low; int j = high; int x = A[ (low+ high) / 2 ] ; do ( while (A[ i]<
x)
++
i;
while
(A[
j]
>x) -- j; wenn ich<=
j)
{
int
temp =
A[
i]
;
A[
i]
=
A[
j]
;
A[
j]
=
temp;
i++;
j--;
}
}
while
(i <
j)
;
if
(low <
j)
qSort(A, low, j)
;
if
(i <
high)
qSort(A, i, high)
;
}
//Algorithmus in Pascal-Sprache procedure qSort(var ar: array of real ; low, high: integer ) ; var i, j: Ganzzahl ; m, wsp: echt ; begin i: = niedrig; j: = hoch; m: = ar[ (i+ j) div 2 ] ; wiederholen while (ar[i] //Algorithmus in Visual Basic-Sprache
//Beim ersten Aufruf muss das 2. Argument gleich 1 sein
//3. Argument muss gleich der Anzahl der Array-Elemente sein Sub qSort(ByVal ar() As double, ByVal low As Integer , ByVal high As Integer ) Dim i, j As Integer Dim m, wsp As double i = low j = high m = ar((i + j) \ 2 ) Tun, bis i > j Tun, während ar(i)< m
i +=
1
Loop
Do
While
ar(j)
>m j -= 1 Schleife If (i<=
j)
Then
wsp =
ar(i)
ar(i)
=
ar(j)
ar(j)
=
wsp
i +=
1
j -=
1
End
If
Loop
If
(low < j)
Then
qSort(ar,
low,
j)
If
(i < high)
Then
qSort(ar,
i,
high)
End
Sub QuickSort ist eine deutlich verbesserte Version des Direktaustausch-Sortieralgorithmus (seine Varianten sind als „Bubble Sort“ und „Shaker Sort“ bekannt), der unter anderem für seine geringe Effizienz bekannt ist. Der grundlegende Unterschied besteht darin, dass die Elemente nach jedem Durchgang in zwei unabhängige Gruppen aufgeteilt werden. Interessante Tatsache: Die Verbesserung der ineffizientesten direkten Sortiermethode führte zu einer effizienten, verbesserten Methode. Vorteile: Mängel: Schnelle Sorte, Hoare-Sorte(englisch Quicksort), oft genannt qsort(namentlich in der C-Standardbibliothek) ist ein bekannter Sortieralgorithmus, den der englische Informatiker Charles Hoare während seiner Arbeit an der Moskauer Staatsuniversität im Jahr 1960 entwickelt hat. Das Sortieren des gesamten Arrays kann durch Ausführen von quicksort(A, 1, length(A)) erfolgen. Bei diesem Schema werden zwei Indizes verwendet (einer am Anfang des Arrays, der andere am Ende), die sich einander annähern, bis ein Elementpaar entsteht, bei dem einer größer als die Referenz ist und sich davor befindet und der zweite kleiner ist und befindet sich danach. Diese Elemente werden vertauscht. Der Austausch findet statt, bis sich die Indizes schneiden. Der Algorithmus gibt den letzten Index zurück. . Das Hoare-Schema ist effizienter als das Lomuto-Schema, da im Durchschnitt dreimal weniger Elemente ausgetauscht werden und die Partitionierung effizienter ist, selbst wenn alle Elemente gleich sind. Ähnlich wie das Lomuto-Schema zeigt auch dieses Schema Wirksamkeit bei Ö(N 2) wenn das Eingabearray bereits sortiert ist. Die Sortierung nach diesem Schema ist instabil. Beachten Sie, dass die Endposition des Referenzelements nicht unbedingt mit dem zurückgegebenen Index übereinstimmt. Pseudocode: Um die Leistung zu verbessern, wenn ein Array eine große Anzahl identischer Elemente enthält, kann eine Prozedur verwendet werden, um das Array in drei Gruppen aufzuteilen: Elemente, die kleiner als das Referenzelement, gleich diesem und größer als dieses sind. (Bentley und McIlroy nennen dies eine „Fat-Partition“. Diese Partition wird in der Funktion verwendet qsort in der siebten Version von Unix. ). Pseudocode: Es ist klar, dass die Aufteilung eines Arrays in zwei Teile relativ zum Referenzelement Zeit braucht. Da alle Partitionierungsoperationen, die mit derselben Rekursionstiefe ausgeführt werden, unterschiedliche Teile des ursprünglichen Arrays verarbeiten, deren Größe insgesamt konstant ist, ist dies auch auf jeder Rekursionsebene erforderlich O(n) (\displaystyle O(n)) Operationen. Folglich wird die Gesamtkomplexität des Algorithmus nur durch die Anzahl der Divisionen, also die Rekursionstiefe, bestimmt. Die Tiefe der Rekursion wiederum hängt von der Kombination der Eingabedaten und der Methode zur Definition des Referenzelements ab. Der beste Fall. In der ausgeglichensten Version wird das Array bei jeder Teilungsoperation in zwei identische (plus oder minus ein Element) Teile geteilt, daher beträgt die maximale Rekursionstiefe, bei der die Größe der verarbeiteten Unterarrays 1 erreicht log 2 n (\displaystyle \log _(2)n). Infolgedessen würde die Anzahl der von Quicksort durchgeführten Vergleiche dem Wert des rekursiven Ausdrucks entsprechen C n = 2 ⋅ C n / 2 + n (\displaystyle C_(n)=2\cdot C_(n/2)+n), was die Gesamtkomplexität des Algorithmus angibt O (n ⋅ log 2 n) (\displaystyle O(n\cdot \log _(2)n)). Durchschnitt. Die durchschnittliche Komplexität bei einer zufälligen Verteilung der Eingabedaten kann nur probabilistisch geschätzt werden. Zunächst muss darauf hingewiesen werden, dass es in der Realität nicht notwendig ist, dass das Trägerelement das Array jedes Mal in zwei Teile teilt identisch Teile. Wenn beispielsweise in jeder Phase eine Unterteilung in Arrays mit einer Länge von 75 % und 25 % des Originals erfolgt, ist die Rekursionstiefe gleich, und dies führt immer noch zu Komplexität. Im Allgemeinen für jeden Fest Beziehung zwischen der linken und rechten Seite der Division ist die Komplexität des Algorithmus gleich, nur mit unterschiedlichen Konstanten. Wir betrachten eine „erfolgreiche“ Aufteilung als eine, bei der das tragende Element zu den zentralen 50 % der Elemente des geteilten Teils der Anordnung gehört; Offensichtlich beträgt die Glückswahrscheinlichkeit bei einer zufälligen Verteilung der Elemente 0,5. Wenn die Teilung erfolgreich ist, beträgt die Größe der zugewiesenen Subarrays nicht weniger als 25 % und nicht mehr als 75 % des Originals. Da jedes zugewiesene Unterarray auch eine Zufallsverteilung aufweist, gelten alle diese Überlegungen für jeden Sortierschritt und jedes Quellfragment des Arrays. Eine erfolgreiche Division ergibt eine Rekursionstiefe von maximal log 4 / 3 n (\displaystyle \log _(4/3)n). Da die Glückswahrscheinlichkeit 0,5 beträgt, erhalten Sie k (\displaystyle k) Im Durchschnitt werden erfolgreiche Trennungen erforderlich sein 2 ⋅ k (\displaystyle 2\cdot k) rekursive Aufrufe des Referenzelements k gehörte einst zu den mittleren 50 % der Gruppe. Wenn wir diese Überlegungen anwenden, können wir daraus schließen, dass die Rekursionstiefe im Durchschnitt nicht größer sein wird 2 ⋅ log 4 / 3 n (\displaystyle 2\cdot \log _(4/3)n), was gleich ist O (log n) (\displaystyle O(\log n)) Und da es auf jeder Rekursionsebene immer noch nicht mehr gibt als O(n) (\displaystyle O(n)) Operationen wird die durchschnittliche Komplexität sein O (n log n) (\displaystyle O(n\log n)). Schlimmsten Fall. In der unausgewogensten Version erzeugt jede Division zwei Unterarrays der Größen 1 und , d. h. bei jedem rekursiven Aufruf ist das größere Array um 1 kürzer als beim vorherigen Mal. Dies kann passieren, wenn in jeder Phase entweder das kleinste oder das größte Element aller verarbeiteten Elemente als Referenzelement ausgewählt wird. Bei der einfachsten Wahl eines Referenzelements – dem ersten oder letzten im Array – wird ein solcher Effekt durch ein bereits sortiertes (in Vorwärts- oder Rückwärtsreihenfolge) Array erzielt; für das mittlere oder jedes andere feste Element das „Worst-Case-Array“. „kann auch speziell ausgewählt werden. In diesem Fall benötigen Sie n − 1 (\displaystyle n-1) Trennvorgänge und die Gesamtbetriebszeit betragen ∑ i = 0 n (n − i) = O (n 2) (\displaystyle \textstyle \sum _(i=0)^(n)(n-i)=O(n^(2))) Operationen, d. h. die Sortierung erfolgt in quadratischer Zeit. Die Anzahl der Wechsel und damit die Betriebszeit sind jedoch nicht der größte Nachteil. Was noch schlimmer ist, ist, dass in diesem Fall die Rekursionstiefe bei der Ausführung des Algorithmus n erreicht, was bedeutet, dass die Rücksprungadresse und die lokalen Variablen der Array-Divisionsprozedur n-mal gespeichert werden. Bei großen Werten von n kann es im schlimmsten Fall zu einer Speichererschöpfung (Stapelüberlauf) kommen, während das Programm läuft. Vorteile: Mängel: Verbesserungen des Algorithmus zielen hauptsächlich darauf ab, die oben genannten Mängel zu beseitigen oder zu mildern, weshalb sie alle in drei Gruppen eingeteilt werden können: Stabilität des Algorithmus, Beseitigung von Leistungseinbußen durch besondere Wahl des Referenzelements und Schutz gegen Call-Stack-Überlauf aufgrund der großen Rekursionstiefe bei erfolglosen Eingabedaten. Wenn ein Programmierer aus praktischen Gründen einen Sortieralgorithmus auswählt, wählt er wahrscheinlich eine Methode namens „Quick Sort“ (auch „qsort“ vom englischen Quick Sort). Es wurde 1960 von dem englischen Wissenschaftler Charles Hoare entwickelt, der sich damals an der Moskauer Staatsuniversität mit maschineller Übersetzung beschäftigte. Der Algorithmus gehört seinem Funktionsprinzip nach zur Klasse der Austauschsortierungen (Shufflesort, Bubblesort usw.) und zeichnet sich durch seine hohe Arbeitsgeschwindigkeit aus. Ein besonderes Merkmal der Schnellsortierung ist die Aufteilung eines Arrays in zwei Teile relativ zu einem Referenzelement. Wenn die Sequenz beispielsweise in aufsteigender Reihenfolge sortiert werden muss, werden alle Elemente, deren Werte kleiner als der Wert des Referenzelements sind, auf der linken Seite platziert, und Elemente, deren Werte größer oder gleich sind Das Referenzelement wird auf der rechten Seite platziert. Unabhängig davon, welches Element als Referenzelement ausgewählt wird, wird das Array sortiert. Die erfolgreichste Situation ist jedoch, wenn auf beiden Seiten des Referenzelements ungefähr die gleiche Anzahl von Elementen vorhanden ist. Wenn die Länge eines der resultierenden Teile ein Element überschreitet, muss er rekursiv geordnet werden, d. h. der Algorithmus muss für jedes der Segmente erneut ausgeführt werden. Daher umfasst der Schnellsortierungsalgorithmus zwei Hauptphasen: Noch einmal zum tragenden Element. Seine Wahl hat keinen Einfluss auf das Ergebnis und kann daher auf ein beliebiges Element fallen. Wie oben erwähnt, wird die größte Effizienz des Algorithmus jedoch erreicht, wenn ein Unterstützungselement ausgewählt wird, das die Sequenz in gleiche oder annähernd gleiche Teile unterteilt. Aufgrund fehlender Informationen ist eine sichere Bestimmung eines solchen Elements jedoch in der Regel nicht möglich, so dass häufig eine zufällige Auswahl eines Referenzelements erforderlich ist. Die folgenden fünf Absätze beschreiben das allgemeine Schema zur Partitionierung eines Arrays (Sortierung in aufsteigender Reihenfolge): Nach dem Teilen der Sequenz sollten Sie die Bedingung überprüfen, um festzustellen, ob eine weitere Sortierung der Teile erforderlich ist. Diese Phase wird später besprochen, aber jetzt werden wir anhand eines konkreten Beispiels das Array aufteilen. Ich habe ein Array von ganzen Zahlen Mas, bestehend aus 8 Elementen (Abb. 5.5): Mas. Ursprünglicher Wert Erste wird 1 sein und zuletzt– 8. Der bestandene Teil wird blau lackiert. Als Referenzelement nehmen wir ein Element mit einem Wert von 5 und einem Index von 4. Wir haben es mit dem Ausdruck berechnet ( Erste+zuletzt)/2, wobei der Bruchteil verworfen wird. Jetzt Mitte=5. Das erste Element auf der linken Seite wird mit verglichen Mitte. Mas>Mitte, somit Erste bleibt gleich 1. Als nächstes werden die Elemente der rechten Seite mit verglichen Mitte. Das Element mit Index 8 und Wert 8 wird geprüft. Mas>Mitte, somit zuletzt verschiebt sich um eine Position nach links. Mas<Mitte, somit zuletzt bleibt gleich 7. Im Moment Erste=1, und zuletzt=7. Das erste und siebte Element sind vertauscht. Beide Zeiger bewegen sich jeweils um eine Position in ihre eigene Richtung. Der Algorithmus geht wieder zum Vergleichen von Elementen über. Das zweite Element wird mit dem Referenzelement verglichen: Mas>Mitte also Erste bleibt gleich 2. Als nächstes werden die Elemente der rechten Seite mit verglichen Mitte. Das Element mit Index 6 und Wert 1 wird geprüft: Mas<Mitte, somit zuletztändert seine Position nicht. Zur Zeit Erste=2, a zuletzt=6. Das zweite und sechste Element sind vertauscht. Beide Zeiger bewegen sich jeweils um eine Position in ihre eigene Richtung. Der Algorithmus geht wieder zum Vergleichen von Elementen über. Das dritte Element wird mit dem Referenzelement verglichen: Mas<Mitte, somit Erste verschiebt sich um eine Position nach rechts. Als nächstes werden die Elemente auf der rechten Seite verglichen Mitte. Das Element mit Index 5 und Wert 9 wird geprüft: Mas>Mitte, somit zuletzt verschiebt sich um eine Position nach links. Jetzt Erste=zuletzt=4, was die Bedingung bedeutet Erste<zuletzt nicht ausgeführt wird, endet die Partitionierungsphase. An diesem Punkt ist die Partitionierungsphase abgeschlossen. Das Array ist relativ zum tragenden Element in zwei Teile geteilt. Es bleibt, seine Teile rekursiv zu ordnen. Wenn einer der aus der Aufteilung des Arrays resultierenden Teile mehr als ein Element enthält, sollten Sie diesen Teil rekursiv ordnen, d. h. die oben beschriebene Aufteilungsoperation für ihn durchführen. Um die Bedingung „Anzahl der Elemente > 1“ zu überprüfen, müssen Sie ungefähr nach folgendem Schema vorgehen: Es gibt ein Array Mas[L..R], Wo L Und R– Indizes der äußersten Elemente dieses Arrays. Am Ende der Partition Zeiger Erste Und zuletzt landete ungefähr in der Mitte der Sequenz und bildete dadurch zwei Segmente: das linke von L Vor zuletzt und direkt von Erste Vor R. Wenn die Bedingung erfüllt ist, ist eine rekursive Sortierung der linken Seite erforderlich L<zuletzt. Für die rechte Seite ist die Bedingung ähnlich: Erste<R. #include „stdafx.h“ #include #include „stdafx.h“ #enthalten #enthalten Verwenden des Namensraums std ; const int n = 7 ; int zuerst, zuletzt; //Sortierfunktion void Quicksort (int * mas, int first, int last) int mid, count; int f = erster, l = letzter; mid = mas [ (f + l ) / 2 ] ; //Berechnen Sie das Unterstützungselement while(mas[f]<
mid
)
f
++
;
while (mas [ l ] > mid ) l -- ; wenn (f<=
l
)
//Neuanordnung von Elementen count = mas [ f ] ; mas[f] = mas[l]; mas[l] = count; f++; l -- ; ), während (f<
l
)
;
wenn (zuerst<
l
)
quicksort
(mas
,
first
,
l
)
;
wenn (f<
last
)
quicksort
(mas
,
f
,
last
)
;
//Hauptfunktion void main() setlocale(LC_ALL, "Rus"); int * A = new int [ n ] ; srand(time(NULL)); cout<<
„Quellarray:“;
für (int i = 0 ; i<
n
;
i
++
)
A[i] = rand() % 10; cout<<
A
[
i
]
<<
" "
;
zuerst = 0 ; last = n - 1 ; Quicksort(A, erster, letzter); cout<<
endl
<<
„Resultierendes Array:“;
für (int i = 0 ; i<
n
;
i
++
)
cout
<<
A
[
i
]
<<
" "
;
A löschen; System ("Pause>>void"); Delphi/Pascal Programm qsort; verwendet crt; const n=7; var A: Array von Ganzzahlen; erster, letzter, i: Ganzzahl; (Sortierverfahren) procedure quicksort(var mas: Array of Integer; First, Last: Integer); var f, l, mid, count: integer; begin f:=first; l:=letzte; mid:=mas[(f+l) div 2]; (Unterstützungselementberechnung) wiederholen, während mas[f] Programm qsort ; verwendet crt ; const n = 7 ; var A: Array [1..n] einer Ganzzahl; erster, letzter, i: ganze Zahl; (Sortierverfahren) procedure quicksort (var mas: array [1..n] of integer; first, last: integer); var f, l, mid, count: integer; beginnen f := zuerst ; l := letzter ; mid := mas [ (f + l ) div 2 ] ; (Referenzelementberechnung) wiederholen während mas[f]<
mid
do
inc
(f
)
;
while mas[l] > mid do dec(l);1. Kleine Unterdateien.
2. Division durch den Median von Drei
3. Nicht rekursive Implementierung.
Zusammenschluss
Direkte Fusion. Bose-Nelson-Algorithmus
Natürliche (Neumann-)Fusion.
Kurze Beschreibung des Algorithmus
Algorithmus
Effizienzzeichen
In der Praxis (wenn Austausche eine teurere Operation sind als Vergleiche) ist Quicksort deutlich schneller als andere Algorithmen mit einem O( N lg N), da die innere Schleife des Algorithmus auf nahezu jeder Architektur effizient implementiert werden kann. 2C N/2 deckt die Kosten für die Sortierung der beiden resultierenden Subarrays ab; N ist der Aufwand für die Verarbeitung jedes Elements mit dem einen oder anderen Zeiger. Es ist auch bekannt, dass der Näherungswert dieses Ausdrucks C N = N log N ist.
Im schlimmsten Fall ergibt sich O( N²) Austausch. Die Anzahl der Wechsel und damit die Betriebszeit sind jedoch nicht der größte Nachteil. Was noch schlimmer ist, ist, dass in diesem Fall die Rekursionstiefe bei der Ausführung des Algorithmus n erreicht, was bedeutet, dass die Rücksprungadresse und die lokalen Variablen der Array-Divisionsprozedur n-mal gespeichert werden. Bei großen Werten von n kann es im schlimmsten Fall dazu kommen, dass der Speicher knapp wird, während der Algorithmus ausgeführt wird. Bei den meisten realen Daten ist es jedoch möglich, Lösungen zu finden, die die Wahrscheinlichkeit, dass quadratische Zeit benötigt wird, minimieren.Verbesserungen
Vorteile und Nachteile
Anmerkungen
Literatur
Ö( N) Hilfsmittel
O(log N) Hilfsmittel (Sedgwick 1978)Hoare-Partition
Sich wiederholende Elemente
Bewertung der Algorithmuskomplexität
Vorteile und Nachteile
Verbesserungen
Der Nachteil aller komplizierten Methoden zur Auswahl eines Stützelements ist der zusätzliche Aufwand; Allerdings sind sie nicht so toll. Array-Aufteilung.
Rekursive Neuordnung
Implementierungen des Quicksort-Algorithmus:
Programmcode in C++:
Programmcode in Pascal:
| In Verbindung stehende Artikel: | |
|
So entfernen Sie Viren von Ihrem Computer, wenn das Antivirenprogramm sie nicht erkennt
Das Problem der Sicherheit mobiler Geräte ist eines der dringendsten ... So wählen Sie einen Benutzernamen auf Twitter aus. Twitter-Name für Mädchen auf Englisch
Nach der Registrierung werden Sie aufgefordert, mehrere schreibende Personen auszuwählen... Präsentation zum Thema „Paint-Grafikeditor“
Diese Lektion richtet sich an diejenigen, die sich mit der Arbeit eines Grafikers vertraut machen möchten... | |
