Beiträge von Mike im Thema „Sortieren in V2 BASIC“
-
-
Hier mal beide Verfahren gut verständlich erklärt.
Bitte melde dich an, um diesen Link zu sehen.
Bitte melde dich an, um diesen Link zu sehen.
Also, es tut mir leid, aber das, was da als "Bucketsort" in dem Video verkauft wird, ist nichts anderes als ein reinrassiger Radixsort.Die Bezeichnung Bucketsort holt sich ihre Berechtigung schon daher, daß die Elemente wie "Tropfen" in einem zugehörigen Eimer gesammelt werden, und man daher eben nicht mehr weiß, woher sie kamen und ob sie sich noch irgendwie unterscheiden. Wenn einem das Eimerbild zu wenig akademisch vorkommt, kann man ja gerne den Zählvorgang zur Namensgebung bemühen, aber warum dann Countingsort und nicht gleich "Countsort"?
Leicht ins Off-Topic abgleitend: genauso ist mir vor ein paar Jahren der Begriff "Code-Reflection" untergekommen. Damit ist wohl eigentlich wahlweise selbstmodifizierender oder dynamisch erzeugter Code gemeint. Eine viel nahelegendere Nutzung des Begriffs, nämlich, daß ein wie auch immer geartetes Programm introspektiv seinen eigenen Code überschaut, um festzustellen was es da eigentlich tut (aus welchem Grund und mit welchem Erfolg auch immer) wird durch so eine Neubelegung nur erschwert. Neusprech haben wir ohnehin schon genug.
-
Meines Erachtens ist es schon ausreichend, wenn die Größe des Wertebereichs (als ganzzahlig angenommen) und die Anzahl der zu sortierenden Daten in der gleichen Größenordnung sind. Bitte sehr:
Code1 N=100:L=1:U=1000:DIMA(N),B(U-L) 2 FORT=1TON:A(T)=INT(RND(1)*(U-L+1))+L:NEXT 3 : 4 T1=TI:REMFORS=0TOU-L:B(S)=.:NEXT 5 FORT=1TON:S=A(T)-L:B(S)=B(S)+1:NEXT 6 T=1:FORS=0TOU-L:IFB(S)THENA=S+L:FORT=TTOT+B(S)-1:A(T)=A:NEXT 7 NEXT:T2=TI 8 : 9 FORT=1TON:PRINTA(T):NEXT:PRINT:PRINTT2-T1
Mit den angegebenen Werten in Zeile 1 (100 Zahlen, Bereich von 1 bis 1000) läuft der Hauptteil - ohne Initialisierung des Feldes B(...) - in ~497 Jiffies durch. Mit Initialisierung von B(...) sind es dann ~773 Jiffies und damit (immer noch) etwa genauso schnell wie mein Combosort mit 100 Elementen.
-
In Bitte melde dich an, um diesen Link zu sehen. hab' ich doch schon eine Variante von Bucketsort implementiert.

-
Zitat von JeeK
[Shellsort], weil einfach und auch N*log(N).
Äh, nein. Je nach Distanzfolge entweder O(N·log²(N)) (<- man beachte das ^2) oder O(N^(1+ε)), wobei ε eine sehr kleine, aber von 0 verschiedene positive Zahl ist.Die Distanzfolge mit den Werten "Feldlänge geteilt durch Zweierpotenzen, nach unten abgerundet" wie in deiner Implementation liegt eher irgendwo zwischen O(N^1,5) und O(N^2): mit deinen drei Datenpunkten komme ich auf O(N^1,29...), was aber vermutlich eher günstig abgeschätzt ist.
Es wird gemutmaßt, daß man mit einer geeigneten Distanzfolge tatsächlich eine Laufzeitordnung von O(N·log(N)) für Shellsort hinbekommen könnte - bislang ist man aber nicht fündig geworden.
(
... ja, ich weiß. ;)) -
Weil's gerade Spaß macht, setzen wir mit Combo-Sort noch einen drauf: bis zu einer Feldgröße von 13 wird Insertion-Sort genommen, darüberhinaus Quicksort. Der Wert 13 wurde empirisch anhand eines Felds mit 100 Zufallszahlen ermittelt, es ergeben sich minimale Laufzeiten in einem recht weiten Bereich von 10..15, also ist die Wahl einigermaßen robust.
Code
Alles anzeigen10 DIML(15),R(15):S=0 11 N=100:DIMA(N) 12 FORT=0TON:A(T)=RND(1):NEXT 13 T1=TI:L=0:R=N:GOSUB20:T2=TI 14 FORT=0TON:PRINTA(T):NEXT 15 PRINTT2-T1 16 END 18 : 19 REM ** COMBO-SORT 20 IFR<=LTHENRETURN 21 IFR-L>13THEN24 22 FORI=L+1TOR:A=A(I):FORJ=I-1TOLSTEP-1:IFA(J)>ATHENA(J+1)=A(J):NEXT 23 A(J+1)=A:NEXTI:RETURN 24 I=L:J=R:X=A((L+R)/2) 25 IFA(I)<XTHENI=I+1:GOTO25 26 IFA(J)>XTHENJ=J-1:GOTO26 27 IFI>JTHEN31 28 A=A(I):A(I)=A(J):A(J)=A 29 I=I+1:J=J-1 30 IFI<=JTHEN25 31 IFJ-L<R-ITHENL(S)=I:R(S)=R:S=S+1:R=J:GOSUB20:GOTO33 32 L(S)=L:R(S)=J:S=S+1:L=I:GOSUB20 33 S=S-1:L=L(S):R=R(S):GOTO20
Hier die Messungen. Diesmal auf dem C64:Code
Alles anzeigenLauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5 Lauf 6 Lauf 7 Lauf 8 N=10: 37 39 38 44 31 17 60 17 N=30: 179 189 162 176 158 91 108 125 N=100: 727 761 789 768 830 350 407 518 N=300: 2671 2790 2701 2922 2753 1433 1603 2263 N=1000: 11724 11105 11597 10687 11653 5821 6401 10083 N=3000: 37230 39902 39587 37961 36916 19806 21542 33584 N=7500: 107118 109806 110337 108261 106426 53932 58240 92677 Läufe 1..5: Zufallsanordnung Lauf 6: aufsteigend sortiert Lauf 7: absteigend sortiert Lauf 8: alle Zahlen gleich
Damit ist die Routine gegenüber der originalen Implementierung von Quicksort nochmal ~25% schneller geworden (zur Erinnerung, Tale-X hatte bei N=100 ca. 1000 Jiffies auf dem C64 gesehen). -
Schön!
Die Zeilen 15 bis 18 lassen sich aber schon etwas kompakter formulieren, wenn man ausnutzt, daß das NEXT einer äußeren Schleife mit explizit benannter Laufvariable alle offenen inneren Schleifen vom Stapel entfernt.

-
So what? Mir ging es in beiden Fällen um den Vergleich der beiden Verfahren in einem Programm. Der Unterschied in der Rechengeschwindigkeit ändert, wie zuvor ja bereits festgestellt, an der Laufzeitordnung nichts. Da nervt mich schon eher, wenn zwei Verfahren nur anhand eines "Datenpunkts" miteinander verglichen werden.
Und jetzt besteht ja immer noch die Möglichkeit, das Originalprogramm nochmal mit Quick- und Bubblesort für die angegebenen Werte für N jeweils 5x auf dem C64 ausführen zu lassen. Wahlweise mit ein- oder ausgeschaltetem Bildschirm- und/oder Sprite-DMA.
Um noch mal auf das Ausgangsposting zurückzukommen: für eine High-Score-Liste ist die Anwendung eines jeden Sortierverfahrens grundsätzlich erstmal wie mit Kanonen auf Spatzen geschossen. "Richtigerweise" hat man eine bereits sortierte Liste vorliegen, sucht mit einem geeigneten Verfahren nach dem richtigen Einfügeplatz, schafft diesen Platz durch Verschieben aller Elemente ab diesem Platz um 1 nach unten und fügt den neuen Score an der freigewordenen Stelle ein.
Wenn aber nun mal gerade ein Bubblesort zur Hand ist, kann man eine Liste mit N+1 Elementen hernehmen, den neuen Score bei Position 1 reinschreiben, sortieren, und ist fertig. Und der Bubblesort in meinem Beispiel ist auch gerade so geschrieben, daß er maximal 2 Durchläufe in diesem Szenario braucht. Zur Darstellung findet man Platz 1 an Position N+1 und Platz N an Position 2. Für N=10 bricht man sich so auch keine Zacke aus der Krone.
Um mal ein anderes Beispiel in den Ring zu werfen: die Simulation einer Ziehung von 6 aus 49. Ziel soll es sein, das Ergebnis sortiert darzustellen und natürlich darf keine Zahl doppelt vorkommen. Da kann man sich auch einigen Blödsinn zusammenprogrammieren, etwa sowas:
Code1 DIMX(6):X(1)=INT(RND(1)*49)+1 2 FORT=2TO6 3 X(T)=INT(RND(1)*49)+1 4 FORS=1TOT-1:IFX(T)=X(S)THEN3 5 NEXTS:NEXT 6 P=0:FORT=1TO5:IFX(T)>X(T+1)THENX=X(T):X(T)=X(T+1):X(T+1)=X:P=-1 7 NEXT:IFPTHEN6 8 FORT=1TO6:PRINTX(T):NEXT
Die Zeilen 1 bis 5 machen die Ziehung, Zeile 4 verwirft Doppel. In den Zeilen 6 und 7 steht der Bubblesort und Zeile 8 macht die Ausgabe.Das geht aber auch etwas flotter und vor allem einfacher wie folgt:
-
-
Mit diesen Überlegungen kommt man dann eben zum Heap-Sort.
Die "Versickern"-Operation, die zum einen zum Aufbau des Heaps hergenommen wird und später auch die Heapstruktur wieder herstellt, kann man in etwa mit dem Binary-Search vergleichen. Sie selbst läuft in O(log(N)) Schritten ab, da die Tiefe des Heaps eben mit dem 2er-Logarithmus von N wächst. Netterweise ist hier die Einfügen-Operation sogar O(1), d.h. geht in konstanter Zeit.

Da zum Aufbau des Heaps und später beim Einfügen in die sortierte Liste N-mal "versickert" werden muß, kommt man halt auf O(Nxlog(N)) als Gesamt-Laufzeitordnung. Dummerweise sieht die "Ideal-Form" des Heaps genau andersherum angeordnet aus, wie später das Ergebnis, und darum gibt es keine richtig günstigen Ausgangsanordnungen für Heap-Sort.
Eine Variante von Heap-Sort (der "Bottom-Up-Heap-Sort") läßt das neue Element von unten her aufsteigen und spart dadurch im Mittel die Hälfte der Vertauschungen gegenüber dem Versickern im Standard-Heap-Sort ein.
-
Mensch, BIF, laß es doch einfach sein!
Dein Code-Fragment erfüllt nicht einmal annähernd die Grundanforderungen, die man an eine Routine stellen müßte, damit man sie als Sortier-Unterprogramm einsetzen könnte. Initialisierung, eigentlicher Sortiervorgang und Ausgabe sind wild miteinander vermischt.
Warum steht in Zeile 10 die Zuweisung "A(M+1)=1E3"?
Warum wird die Routine ab Zeile 20 9x aufgerufen?
Warum listet sich das Programm selbst auf?
Warum hängt der Bereich der erzeugten Zufallszahlen in Zeile 20 von der Anzahl der zu sortierenden Zahlen ab?
Alles Fragen von denen ich weiß, daß Du sie nicht beantworten kannst und willst. Ersteres, weil es eben für diese ungeklärten Tatsachen eben keine hinreichenden Gründe gibt, und letzteres, weil es deinem Trollschema entspricht.
> \ignore
-
Zitat von Cyberdyne
Hallo? Hast du eigentlich gelesen, was ich geschrieben habe?
Klar hab' ich das.Es ist ja schön, daß Bubblesort bei (nahezu) korrekt sortierten Listen in die Nähe der linearen Laufzeitordnung kommt, das kriegt meine einfache Version aber auch schon hin und ist bei einer tatsächlich korrekt sortierten Liste optimal. Jede weitere Optimierung an Bubblesort halte ich für Zeitverschwendung.
-
Zitat von Bytebreaker
Heute hat mir ein Entwickler aus meiner Firma erzählt, Bubblesort wird irgendwann [irgendwas] bei bestimmten Sortiermengen.
Das fällt wohl eher unter die Kategorie Ammenmärchen.Cyberdyne,
am Bubblesort kannst Du noch ewig rumoptimieren, von der Idee kommt man aber schnell ab, wenn man mal einen laufenden Quicksort zur Hand hat und die beiden gegeneinander antreten läßt.
Die Version von Quicksort hier nimmt einfach das mittlere Element eines Sortierbereiches als Pivot her und fällt darum nicht gerade bei bereits vorsortierten Feldern mit quadratischer Laufzeit auf die Nase. Weiterhin wird immer das kleinere Unterfeld als erstes sortiert, auf diese Weise minimiert man den nötigen Stapelspeicher. DIMS(31) reicht für 65535 Elemente. In Zeile 11 kann N geändert und in Zeile 13 mit GOSUB20 oder GOSUB50 zwischen Bubble- und Quicksort gewechselt werden:
Code
Alles anzeigen10 DIMS(31):SP=0:REM ** STACK FOR QUICK-SORT 11 N=10:DIMA(N) 12 FORT=0TON:A(T)=RND(1):NEXT 13 T1=TI:L=0:R=N:GOSUB50:T2=TI 14 FORT=0TON:PRINTA(T):NEXT 15 PRINTT2-T1 16 END 18 : 19 REM ** BUBBLE-SORT 20 IFR<=LTHENRETURN 21 F=0:FORT=LTOR-1:IFA(T)>A(T+1)THENA=A(T):A(T)=A(T+1):A(T+1)=A:F=1 22 NEXT:IFFTHEN21 23 RETURN 29 : 49 REM ** QUICK-SORT 50 IFR<=LTHENRETURN 51 I=L:J=R:X=A((L+R)/2) 52 IFA(I)<XTHENI=I+1:GOTO52 53 IFA(J)>XTHENJ=J-1:GOTO53 54 IFI>JTHEN57 55 A=A(I):A(I)=A(J):A(J)=A 56 I=I+1:J=J-1 57 IFI<=JTHEN52 58 IFJ-L<R-ITHENS(SP)=I:S(SP+1)=R:SP=SP+2:R=J:GOSUB50:GOTO60 59 S(SP)=L:S(SP+1)=J:SP=SP+2:L=I:GOSUB50 60 SP=SP-2:L=S(SP):R=S(SP+1):GOTO50
Bis N=10 liegen die beiden etwa gleichauf, Bubblesort ist vielleicht sogar schneller, aber schau mal was für größere N passiert:Dies sind die Laufzeiten in 1/60 Sekunden (Jiffies):
Code
Alles anzeigenQuick-Sort N Lauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5 10 56 65 60 61 59 30 230 221 231 211 207 100 837 881 867 849 858 300 3029 3169 3054 2969 2960 1000 12032 11954 11941 12553 12266 Bubble-Sort N Lauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5 10 66 47 93 82 64 30 563 501 684 633 627 100 6268 6918 6837 7474 6622 300 62476 57756 ... so langsam sollt's klar werden 1000 nicht ausprobiert, erwartete Laufzeit ~600000..700000 Jiffies.
Das einzig Gute am Bubblesort ist, daß man ihn wirklich schnell hingeschrieben bekommt, wenn man die "Optimierungen" wegläßt. Und wie Deep4 ja schon vorgeführt hat, ist ein Sortier-Algo schnell mal verbockt - einwandfreie Funktion ist hier aber das höchste Gut! -
Morgen zusammen!

Bytebreaker,
die meisten naiven Sortierverfahren haben ja quadratisches Laufzeitverhalten (d.h. brauchen in etwa die vierfache Zeit bei der doppelten Menge an zu sortierenden Zahlen, die 9-fache Zeit bei der 3-fache Menge, etc.) was kurz mit O(n²) notiert wird. Deins geht mit O(n³), da drei Schleifen über die volle Anzahl ineinander geschachtelt sind.
Üblicherweise setzt sich ein Sortieralgorithmus aus zwei relevanten Teilen zusammen: es werden zwei Elemente (nicht notwendig benachbart!) miteinander verglichen, und wenn sie verkehrtherum angeordnet sind, werden sie getauscht.
Macht man das z.B. systematisch wiederholend mit allen Feldpaaren von vorne nach hinten, und hört erst dann auf, wenn alle Elemente richtig sortiert sind, dann erhält man den Bubblesort:
Code10 N=10:DIMX(N):FORT=1TON:X(T)=RND(1):NEXT 11 : 12 P=0:FORT=1TON-1:IFX(T)>X(T+1)THENX=X(T):X(T)=X(T+1):X(T+1)=X:P=-1 13 NEXT:IFPTHEN12 14 : 15 FORT=1TON:PRINTX(T):NEXT
Der Algorithmus hat seinen Namen daher, daß die Zahlen wie Blasen im Feld aufsteigen. Eine Zahl steigt so lange, bis sie von einer größeren Zahl aufgehalten wird, dann steigt letztere dafür dann weiter auf. Falls denn mindestens eine Vertauschung stattgefunden hat, wird erneut die FOR-Schleife ausgeführt.Nach dem ersten Durchlauf der FOR-Schleife steht somit auf jeden Fall die größte Zahl im letzten Feldelement. Nach dem zweiten Durchlauf (sofern er denn nötig war), die zweitgrößte Zahl im vorletzten Feldelement. Und so weiter. Das heißt, die FOR-Schleife selbst wird maximal N mal ausgeführt, und darum ist die Laufzeit im Mittel und auch im ungünstigsten Fall quadratisch. Im günstigsten Fall läuft die FOR-Schleife nur einmal durch und stellt dabei fest, daß alle Zahlen richtig sortiert sind und ist dann fertig.
Es gibt bessere Algorithmen, die dann auch nicht nur unbedingt benachbarte Feldelemente vertauschen und die Auswahl der zu vergleichenden und tauschenden Elemente auch an Hand der zuvor getauschten Elemente festlegen, doch die sind programmtechnisch komplizierter: Quicksort z.B. hat die notorische Eigenschaft, daß er bei kleinsten Änderungen im Code auch schon mal "kaputtgeht", den muß man also besonders vorsichtig implementieren.
Für kleine Elementanzahlen bis etwa 20 ist ein Bubblesort völlig unproblematisch verwendbar, und meistens genauso schnell wie die etwas intelligenteren Sortierverfahren.