Vergleich von Austauschsortierungsalgorithmen

Dieser Artikel beschreibt verschiedene Optionen zum Sortieren von Austauschen und beschreibt eine einfache grafische Anwendung ( process.js ) mit Beispielen für Sortierungen.

Vor dem Lesen empfehle ich Ihnen, die Artikel des Benutzers valemak zu lesen :

→ Exchange-Sortierung
→ Blasensortierung und Alles-Alles-Alles
→ Dumme Sorte und andere klügere

Blasensortierung

Die einfachste Möglichkeit besteht darin, das Array vom ersten bis zum letzten Element zu durchlaufen und (falls erforderlich) benachbarte Elemente auszutauschen.

→ Überprüfen Sie hier


Um den Schieberegler zu bewegen, müssen Sie auf die graue Schaltfläche in der unteren linken Ecke klicken.
Wenn Sie auf die Schaltfläche klicken, bewegen Sie den Schieberegler einen Schritt nach rechts

slider++; 

Als nächstes prüfen wir: Haben wir das Ende des Arrays erreicht (dann springen wir zum Anfang) und vergleichen (tauschen) benachbarte Elemente aus


Processing.js verwendet Java-Datenstrukturen. Anschließend wird der Code in Javascript ( Link ) übersetzt. Die Deklaration eines Arrays von Instanzen der Module-Klasse, die für das Rendern von Elementen und das Initialisieren der Instanzen verantwortlich ist, erfolgt folgendermaßen

Die Hauptfunktion beim Zeichnen von void draw () ist eine Endlosschleife, in der Klasseninstanzen sortiert werden

 for (Module mod : mods) { mod.display(); } 

Fügen Sie die Funktion randFoo () hinzu , die zufällige Werte zurückgibt. Um sicherzustellen, dass sich die Werte nicht wiederholen, fügen wir sie ArrayLis t in der listRand- Liste hinzu und überprüfen in der Funktion randFoo () , ob die neue Zufallszahl in der listRand- Liste enthalten ist

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; } 

→ Überprüfen Sie hier

Pixelsortierung

Die Pixelsortierung (hier) ist eine Implementierung der Blasensortierung.
Wir werden die wärmeren / helleren Pixel auf die eine Seite und die dunkleren / kälteren auf die andere Seite verschieben

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} } 

→ Überprüfen Sie hier
Um mit dem Sortieren zu beginnen, klicken Sie auf das Bild und halten Sie die Taste gedrückt.
Weitere Informationen zu Pixelsorten finden Sie hier .
Video über die Pixelsortierung auf dem offiziellen Kanal The Coding Train hier

Begrenzer und Flagge

Sie können die Anzahl der Iterationen reduzieren, wenn Sie nicht über bereits sortierte Elemente iterieren. Fügen Sie dazu am Ende des Arrays einen Begrenzer hinzu , der nach jeder Iteration an den Anfang des Arrays verschoben wird

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; } 

→ Überprüfen Sie hier

Eine weitere Möglichkeit, die Anzahl der Büsten zu verringern, finden Sie im Artikel Bubble Sort (Wikipedia). Wenn wir während des Durchlaufs des Arrays niemals die benachbarten Elemente gewechselt haben, wird das Array sortiert und der Zyklus kann abgeschlossen werden ( Iverson- Bedingung).

Fügen Sie ein Flag- Flag hinzu , das ausgelöst wird, wenn wir auf einige Elemente treffen, die ausgetauscht werden müssen. Wenn das Flag gesetzt ist, durchlaufen Sie das Array erneut. Wenn nicht, beenden Sie den Zyklus. Der Status des Flags wird in der Konsole angezeigt.



→ Überprüfen Sie hier

Wenn Sie links einen Begrenzer platzieren und ein Element mit einem Begrenzer als Referenz / Minimum verwenden, wird nach Auswahl sortiert.

Fügen Sie die min- Variable hinzu, in die der Mindestwert geladen wird. Angenommen, das Element ganz links ist anfangs minimal: Wenn ein Element während des ersten Durchlaufs des Arrays kleiner als das Minimum ist, speichern wir dieses Element selbst in der Variablen min

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; } 

Tauschen Sie dann das erste Element und das Minimum aus

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; } 

Wenn der Schieberegler den rechten Rand des Arrays erreicht, bewegt sich der Begrenzer einen Schritt nach rechts und der Schieberegler zum Begrenzer

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; } 

→ Überprüfen Sie hier
Die Anzahl der Kennzahlen kann reduziert werden, wenn zu Beginn der Suche das aktuelle Element und das am weitesten rechts stehende Element des Arrays verglichen (ausgetauscht) werden

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; } 

Dann können Sie das Element ganz rechts im Array nicht überprüfen

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++; 

→ Überprüfen Sie hier

Hier können Sie die Sortierung des rechten Teils des Arrays in absteigender Reihenfolge hinzufügen, indem Sie das maximale Element max hinzufügen - wir erhalten die Shaker-Sortierung nach Auswahl. Siehe den Abschnitt zum Sortieren von Schüttlern am Ende des Artikels.

Schnelle Sortierung

Der Auswahlmechanismus für Stützelemente wird auch beim schnellen Sortieren verwendet. Dieser Algorithmus beinhaltet die Auswahl des anfänglichen Referenzelements, mit dem alle anderen Elemente des Arrays verglichen werden. Die Ausführungszeit des Algorithmus hängt von der Wahl des Anfangselements ab. Im obigen GIF ist das Startelement Nummer 3 . Weitere Informationen zur Auswahl des Startunterstützungselements finden Sie im Artikel (Wikipedia).
Ein Video zur schnellen Sortierung ist auf dem offiziellen Youtube-Kanal der Verarbeitungs- und p5.js- Sprachen verfügbar. Hier sehen Sie die Visualisierung des Algorithmus.
Wenn das erste Element einfach ist, können Sie Elemente einfügen, die kleiner als das grundlegende Element davor sind. Dann wird das Array in zwei Teile unterteilt. Die Elemente links sind kleiner als das grundlegende Element rechts - mehr. Informationen zu einer solchen Methode finden Sie im folgenden Abschnitt zum Sortieren nach Einfügungen.

Zwergsort

Im Wesentlichen betrachtet der Gnom die nächsten und vorherigen Gartentöpfe: Wenn sie in der richtigen Reihenfolge sind, tritt er einen Topf vor, andernfalls tauscht er sie aus und tritt einen Topf zurück.

Speichern Sie nach dem Anheben des Flags die Koordinate des Schiebereglers in der Variablen limiterR und bringen Sie den Schieberegler schrittweise an den Anfang des Arrays zurück

 slider--; 

Setzen Sie am Anfang des Arrays das Flag zurück und setzen Sie den Schieberegler mit der Koordinate, die wir in der Variablen limiterR gespeichert haben, in die Zelle

 if(slider==0){ flag=false; slider=limiterR; } 

→ Überprüfen Sie hier

Durch Ändern dieses Algorithmus erhalten wir " Sortieren nach Einfügungen ".
Beim Sortieren nach Einfügungen wird das Referenz- / Mindestelement ausgewählt, und im unsortierten Teil des Arrays wird das Element ausgewählt, das kleiner als die Referenz ist und vor der Referenz eingefügt wird

Lassen Sie uns die minimalen Elementaustauschplätze mit den vorherigen bis zur Referenz usw. haben. vor der Referenz eingefügt .
Fügen Sie eine Bedingung hinzu

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; } 

→ Überprüfen Sie hier


Schnelle Einfügesortierung

Bei diesem Algorithmus wird das Array durch das unterstützende Element in zwei Teile geteilt.
Das erste Element sei die Referenz: Vergleichen Sie ab dem zweiten die Elemente des Arrays mit der Referenz, wenn ein Element kleiner als die Referenz ist

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

Fügen Sie das vor der Referenz gefundene Element ein

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; } 

Wenn die Flagge gehisst wird, bewegen Sie den Schieberegler schrittweise nach links, bis wir auf das Stützelement treffen

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } } 

T.O. Das Array ist links in zwei Teile unterteilt - die Elemente sind kleiner als die Referenz, rechts - mehr

→ Überprüfen Sie hier

Wenn nach jeder Aufzählung die Koordinaten des Unterstützungselements in ext gespeichert werden. pivotsArr- Array. Wenn das Referenzelement den rechten Rand erreicht, wird ein Array nach Ebene / Schritt sortiert. Elemente auf jeder nächsten Ebene sind größer als Elemente auf der vorherigen Ebene. Die Grenzen der Ebenen werden in add enthalten sein. pivotsArr- Array
Jedes Mal, wenn Sie auf die Schaltfläche klicken, geben wir das pivotsArr- Array an die Konsole aus

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); } 

Fügen Sie am Ende des Programms die Zufallsfunktion randFoo () hinzu .

→ Überprüfen Sie hier

Jetzt müssen Sie die Elemente jeder Ebene separat sortieren (es bleibt nur die Bedingung zum Beenden des Zyklus hinzuzufügen).

→ Überprüfen Sie hier
Diese Sortierung kann als Sortierung nach Ebene beschrieben werden.
Da die numerischen Daten nach jeder Aufzählung in Ebenen angeordnet sind, überschreiten die Nummern jeder nächsten Ebene die Nummern der vorherigen.

Ungerade-gerade Sortierung

Wir werden den Schieberegler um zwei Schritte bewegen und benachbarte Elemente vergleichen

 slider=slider+2; 

T.O. Wir vergleichen die Elemente 0 und 1, 2 und 3, 4 und 5, 6 und 7 usw.
Wenn der Schieberegler den Rand des Arrays erreicht, lassen Sie den Begrenzer einen Schritt nach links und den Schieberegler zum Anfang des Arrays fahren.
Als nächstes vergleichen wir die Elemente 1 und 2, 3 und 4, 5 und 6, 7 und 8 usw.
Nachdem wir den Limiter erreicht haben, verschieben wir ihn einen Schritt nach rechts und setzen den Schieberegler an den Anfang des Arrays.

→ Überprüfen Sie hier

Haarbürste sortieren

Lassen Sie den Schieberegler am Anfang des Arrays und das rechte Trennzeichen am Ende stehen. Elemente vergleichen (tauschen). Wir verschieben den Limiter einen Schritt nach links und speichern seinen Index in der Variablen limiterStore

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

Bewegen Sie den Schieberegler mit dem Stopp schrittweise an das Ende des Arrays

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; } 

Nachdem Sie das Ende des Arrays als Begrenzer erreicht haben, setzen Sie den Schieberegler an den Anfang des Arrays und setzen Sie den Begrenzer in limiterStore-1

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

→ Überprüfen Sie hier

Shaker sortieren

Fügen Sie den linken Begrenzer limiterL am Anfang des Arrays hinzu.
Lassen Sie die Flaggenflagge steigen, wenn der Schieberegler den rechten Begrenzer LimiterR erreicht , und bewegt sich der Limiter einen Schritt nach links. Wenn die Flagge gehisst wird, bewegt sich der Schieberegler schrittweise zurück zum linken Begrenzer. Der Begrenzer bewegt sich einen Schritt nach rechts. Der Schieberegler bewegt sich schrittweise nach rechts


→ Überprüfen Sie hier

Shaker nach Wahl sortieren
Fügen Sie der Blasensortierung mit dem rechten Begrenzer den linken Begrenzer hinzu. Bei jeder Verschiebung des Schiebereglers nach rechts prüfen wir (Swap), was größer ist - das aktuelle Element oder der aktuelle Begrenzer

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; } 

Wenn der Schieberegler den rechten Begrenzer LimiterR erreicht , bewegt sich der rechte Begrenzer einen Schritt nach links, der linke Begrenzer bewegt sich einen Schritt nach rechts, der Schieberegler kehrt zum linken Begrenzer zurück

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; } 

→ Überprüfen Sie hier

PS Hier wird eine Anwendung beschrieben, die das Studium von Algorithmen und Datenstrukturen viel interessanter macht .
Eine weitere Visualisierung einer Reihe von Algorithmen und Datenstrukturen.
In diesem Artikel wird eine andere Site erwähnt, auf der Sie sehen können, wie Daten nach verschiedenen Algorithmen sortiert werden.
Dieser Artikel gibt eine Einschätzung der Komplexität der Blasensortierung.
Weitere Informationen zur Komplexitätsbewertung finden Sie hier , hier , hier , hier .