HOPASA-Sort 2 (HOld Position And Shove Away) Home Daten Name:  HOPASA-Sort 2 Typ:  Hybrid-Sortierverfahren Autor:  Martin Oppermann Idee:  1988 Programmiert:  1988 Veröffentlichung:  11.7.2021 Arbeitsweise:  - In-Place - vergleichsbasierend rekursiv:  nein stabil:  nein      Inhaltsverzeichnis 1.  Beschreibung 2.  Funktionsbeschreibung 3.  Der Quellcode   3.1  Index der Variablen   3.2  Der Quellcode mit "GOTO"-Befehl   3.3  Der Quellcode ohne "GOTO"-Befehl 4.  Hinweise zum Urheberrecht Beschreibung Dies ist der Quellcode des instabilen Hybrid-Sortierverfahrens "HOPASA-Sort 2", das ich im Jahr 1988, im Alter von 14 Jahren, mit dem BASIC des Commodore Plus/4, als Unterprogramm entwickelt habe. HOPASA-Sort 2 ist der Nachfolger des Sortierverfahrens "HOPASA-Sort", das ich bereits zwei Jahre zuvor entwickelt hatte und dessen Funktionsweise fast vollständig mit der von Insertionsort identisch ist. Der Unterschied von HOPASA-Sort zu HOPASA-Sort 2 besteht darin, dass HOPASA-Sort 2 in der ersten Hälfte des Arrays zusätzlich die vorderen Datensätze / Zahlen, mit denen der hinteren der zweiten Hälfte des Arrays vergleicht und gegebenenfalls vertauscht. Dies hat eine ganz enorme Beschleunigung der Arbeitsgeschwindigkeit zufolge und auch das spiegeln des Arrays ("Worst-Case"-Fall), ist bereits beim Erreichen der Hälfte des Arrays abgeschlossen. In der zweiten Hälfte des Arrays, arbeitet HOPASA-Sort 2 dann mit einem weiteren Sortierverfahren, fast genauso wie Insertionsort. (!)  Es gibt eine Möglichkeit HOPASA-Sort 2 noch deutlich schneller zu machen. Im Quellcode (siehe unten) gibt es zwei Stellen (Schritt 4 und 5), in denen sich die zu verschiebenden Elemente dadurch bewegen, indem immer zwei benachbarte Elemente, in jeweils drei Schritten, miteinander vertauscht werden. (TEMP = Element "A" / Element "A" = Element "B" / Element "B" = TEMP) Das ist praktisch die gleiche Arbeitsweise, wie bei einem rückwärtslaufenden Bubblesort. Wenn man den Quellcode so ändert, dass die Verschiebung wie bei Insertionsort abläuft, dann könnte man die Arbeitsgeschwindigkeit um etwa 50% erhöhen. Bei Insertionsort wird das zu verschiebende Element zuerst auf TEMP gelegt und solange die richtige Position noch nicht gefunden wurde, wird Element "B" immer nur mit Element "A" überschrieben und zum Schluss, an der richtigen Stelle, Element "A" mit TEMP. (!)  Aufgrund der Funktionsweise eignet sich HOPASA-Sort 2 trotz seines langen Programmcodes hervorragend dazu, Insertionsort innerhalb von Shellsort zu ersetzen. Home / Oben Funktionsbeschreibung HOPASA-Sort 2 sortiert nicht nur das komplette Array, sondern kann beim Start mit den Variablen "L" (links) und "R" (rechts), auch nur einen Teil des Arrays sortieren. Schritt 1: Der Programmablauf beginnt mit einer Sicherheitsüberprüfung, die in Pseudo- und Quellcodes immer wieder vergessen wird, nämlich der Überprüfung, ob mindestens zwei zu sortierende Datensätze / Zahlen vorhanden sind. Ist das nicht der Fall, dann ist die Sortierung beendet. Schritt 2: Im zweiten Schritt werden das erste und letzte zu sortierende Element (Datensatz / Zahl) verglichen und gegebenenfalls vertauscht. Egal ob dieser Fall eingetreten ist oder nicht, ist die Anzahl der zu sortierenden Elemente = 2, dann ist die Sortierung anschließend beendet. Schritt 3: Im dritten Schritt wird überprüft, ob die Anzahl der zu sortierenden Elemente = 3 ist. Ist dies der Fall, dann wird die Variable "M" (Mitte des Arrays) auf den Wert L - 1 gesetzt und der Programmablauf springt direkt zum Programmablauf der zweiten Hälfte des Arrays (Schritt 5). Durch die Variable "M" werden hier nun aber die erste und zweite Hälfte des Arrays, als Ganzes sortiert. Der dritte Schritt ist zwingend erforderlich, weil es bei drei zu sortierenden Elementen, aufgrund der Arbeitsweise der Sortierung der ersten Hälfte des Arrays (Schritt 4), zu überflüssigen Vertauschungen von Elementen kommen würde. Schritt 4: Im vierten Schritt wird die erste Hälfte des Arrays sortiert, indem kleinere Datensätze / Zahlen im Array, bis zu ihrer richtigen Position nach vorne rutschen, indem immer zwei benachbarte Elemente vertauscht werden. Die Variable "M" (Mitte des Arrays) enthält hierbei die Position des letzten Elements, in der ersten Hälfte des Arrays. Bei einer ungeraden Anzahl von zu sortierenden Elementen, hat die Variable "M" immer die Position des Elements vor der Mitte. Zusätzlich werden vor jedem neuen zu überprüfenden Element, zuvor das nachfolgende Element und das Element verglichen, das sich spiegelverkehrt an der anderen Seite des Arrays befindet und gegebenenfalls vertauscht. Dies hat eine ganz enorme Beschleunigung der Arbeitsgeschwindigkeit zufolge und auch das spiegeln des Arrays ("Worst-Case"-Fall), ist bereits beim Erreichen der Hälfte des Arrays abgeschlossen. Schritt 5: Im fünften und letzten Schritt, wird das Array von der Position des Elements "M" + 1 aus, mit einem weiteren Sortierverfahren bis zum Ende sortiert. Regulär wird hierbei nur die zweite Hälfte des Arrays sortiert, im Fall von drei zu sortierenden Elementen, jedoch als Ganzes zusammen mit der ersten Hälfte. Während der Sortierung rutschen kleinere Datensätze / Zahlen im Array - wie auch im Schritt 4 - so lange durch das Vertauschen zweier benachbarter Elemente nach vorne durch das Array, bis sie ihre richtige Position erreicht haben. Verständlicherweise können sie sich dabei natürlich auch durch die erste Hälfte des Arrays bewegen. Home / Oben Der Quellcode Index der Variablen (alphabetisch) I:  main loop / Hauptschleife Ib:  beside loop / Nebenschleife L:  left / links = Anfang des zu sortierenden Bereichs im Array M:  middle of the array / Mitte des zu sortierenden Bereichs im Array N:  number of elements / Anzahl der zu sortierenden Elemente R:  right / rechts = Ende des zu sortierenden Bereichs im Array TEMP:  temporary auxiliary variable / temporäre Hilfsvariable Home / Oben Der Quellcode mit "GOTO"-Befehl Sub HOPASAsort2[field Array , L , R] ; ==== HOPASA-Sort 2 (HOld Position And Shove Away) ================================================ ;             Name: HOPASA-Sort 2 ;              Typ: Sortierverfahren ;            Autor: Martin Oppermann ;             Idee: 1988 ;     Programmiert: 1988 ; Veröffentlichung: 11.7.2021 ;     Arbeitsweise: In-Place ;         rekursiv: nein ;           stabil: nein ; Siehe: http://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/HOPASA-Sort_2.php Dim I As Long Dim Ib As Long Dim M As Long Dim N As Long Dim TEMP As Long ; ==== Schritt 1: Es muss mindestens zwei zu sortierende Elemente geben ============================ N = R - L + 1 ; ---- Ende wenn Anzahl der Elemente < 2 ---- If N < 2 Then Exit Sub ; ==== Schritt 2: Vertausche gegebenenfalls das erste und letzte Element =========================== If Array[L] > Array[R] Then         TEMP = Array[L]         Array[L] = Array[R]         Array[R] = TEMP End If ; ---- Ende wenn Anzahl der Elemente = 2 ---- If N = 2 Then Exit Sub ; ==== Schritt 3: Überspringe die Sortierung der ersten Hälfte, wenn Anzahl der Elemente = 3 ======= If N = 3 Then         M = L - 1         GoTo HOPASAsort2_middle End If ; ==== Schritt 4: Die linke Hälfte des Arrays sortieren ============================================ M = L + Int[N / 2] - 1 For I = L To M ; ---- Vertausche gegebenenfalls das nächste und gespiegelte Element ---- If Array[I + 1] > Array[R + L - I - 1] Then         TEMP = Array[I + 1]         Array[I + 1] = Array[R + L - I - 1]         Array[R + L - I - 1] = TEMP End If ; ---- Elemente gegebenenfalls nach vorne verschieben ---- If Array[I] > Array[I + 1] Then         For Ib = I To L Step -1         If Array[Ib] > Array[Ib + 1] Then                 TEMP = Array[Ib]                 Array[Ib] = Array[Ib + 1]                 Array[Ib + 1] = TEMP         Else                 GoTo HOPASAsort2_loop1         End If         Next Ib End If HOPASAsort2_loop1: Next I ; ==== Schritt 5: Die rechte Hälfte des Arrays sortieren =========================================== HOPASAsort2_middle: For I = M + 1 To R - 1 ; ---- Elemente gegebenenfalls nach vorne verschieben ---- If Array[I] > Array[I + 1] Then         For Ib = I To L Step -1         If Array[Ib] > Array[Ib + 1] Then                 TEMP = Array[Ib]                 Array[Ib] = Array[Ib + 1]                 Array[Ib + 1] = TEMP         Else                 GoTo HOPASAsort2_loop2         End If         Next Ib End If HOPASAsort2_loop2: Next I End Sub Home / Oben Der Quellcode ohne "GOTO"-Befehl (Arbeitet gemessen etwa 22,5% langsamer) Sub HOPASAsort2[field Array , L , R] ; ==== HOPASA-Sort 2 (HOld Position And Shove Away) ================================================ ;             Name: HOPASA-Sort 2 ;              Typ: Sortierverfahren ;            Autor: Martin Oppermann ;             Idee: 1988 ;     Programmiert: 1988 ; Veröffentlichung: 11.7.2021 ;     Arbeitsweise: In-Place ;         rekursiv: nein ;           stabil: nein ; Siehe: http://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/HOPASA-Sort_2.php Dim I As Long Dim Ib As Long Dim M As Long Dim N As Long Dim TEMP As Long ; ==== Schritt 1: Es muss mindestens zwei zu sortierende Elemente geben ============================ N = R - L + 1 ; ---- Ende wenn Anzahl der Elemente < 2 ---- If N < 2 Then Exit Sub ; ==== Schritt 2: Vertausche gegebenenfalls das erste und letzte Element =========================== If Array[L] > Array[R] Then         TEMP = Array[L]         Array[L] = Array[R]         Array[R] = TEMP End If ; ---- Ende wenn Anzahl der Elemente = 2 ---- If N = 2 Then Exit Sub ; ==== Schritt 3: Überspringe die Sortierung der ersten Hälfte, wenn Anzahl der Elemente = 3 ======= M = L - 1 If N > 3 Then ; ==== Schritt 4: Die linke Hälfte des Arrays sortieren ============================================         M = L + Int[N / 2] - 1         For I = L To M ; ---- Vertausche gegebenenfalls das nächste und gespiegelte Element ----         If Array[I + 1] > Array[R + L - I - 1] Then                 TEMP = Array[I + 1]                 Array[I + 1] = Array[R + L - I - 1]                 Array[R + L - I - 1] = TEMP         End If ; ---- Elemente gegebenenfalls nach vorne verschieben ----         If Array[I] > Array[I + 1] Then                 Ib = I                 Do                 If Array[Ib] > Array[Ib + 1] Then                         TEMP = Array[Ib]                         Array[Ib] = Array[Ib + 1]                         Array[Ib + 1] = TEMP                 Else                         Ib = 0                 End If                 Ib = Ib - 1                 Loop Until Ib < L         End If         Next I End If ; ==== Schritt 5: Die rechte Hälfte des Arrays sortieren =========================================== For I = M + 1 To R - 1 ; ---- Elemente gegebenenfalls nach vorne verschieben ---- If Array[I] > Array[I + 1] Then         Ib = I         Do         If Array[Ib] > Array[Ib + 1] Then                 TEMP = Array[Ib]                 Array[Ib] = Array[Ib + 1]                 Array[Ib + 1] = TEMP         Else                 Ib = 0         End If         Ib = Ib - 1         Loop Until Ib < L End If Next I End Sub Home / Oben Hinweise zum Urheberrecht Alle Codes von HOPASA-Sort 2, dürfen von allen Personen / Firmen / Unternehmen uneingeschränkt verwendet werden und auch auf andere Internetseiten hochgeladen werden. Sowohl in unveränderter Form, modifiziert, oder an andere Programmiersprachen angepasst. Das schließt auch schriftliche Publikationen in Fachliteratur, Magazinen, Tageszeitungen, Zeitschriften, oder sonstigen Druckerzeugnissen mit ein. In Videos im Internet, oder in Beiträgen / Dokumentationen / Sendungen im Fernsehen / Spielfilmen, dürfen die Codes ebenfalls gezeigt werden. Die Codes bleiben aber trotzdem mein geistiges Eigentum. Daher möchte ich - Martin Oppermann - als Autor genannt werden und es wäre schön, wenn ein Link zu der folgenden Datei auf meiner Internetseite gesetzt werden würde: http://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/HOPASA-Sort_2.php Home / Oben / Impressum / Datenschutzerklärung   Diese Internetseite wurde für eine Auflösung von 2160 x 1440 Bildschirmpunkten und eine Anzeige-Skalierung von 150% optimiert.