Beiträge von Mike im Thema „Sortieren in V2 BASIC“

    Zitat von Tale-X

    Sehr schön! Die Geschwindigkeit ist beeindruckend [...]


    Allerdings hab' ich hier auch schon darauf geachtet, daß möglichst wenig Index-Arithmetik stattfindet. Ansonsten ließe die Routine nämlich schnell ein paar hundert Jiffies liegen.

    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:

    Code
    1 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. :)

    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.

    (:spassbremse: ... 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.


    Hier die Messungen. Diesmal auf dem C64:


    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:

    Code
    1 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:

    Code
    1 DIMX(49):FORT=1TO6
    2 X=INT(RND(1)*49)+1:IFX(X)=1THEN2
    3 X(X)=1:NEXT
    4 FORT=1TO49:IFX(T)=1THENPRINTT
    5 NEXT
    Zitat von JeeK

    Die zuvor genannten Werte für Quicksort konnte ich nicht nachvollziehen - kommen mir zu niedrig vor.


    Oh. Ich vergaß zu erwähnen, daß ich die Zeiten Bitte melde dich an, um diesen Link zu sehen. auf einem VC-20 genommen hatte. :whistling:

    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:


    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):


    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:

    Code
    10 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.