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

    Cyberdynes Ausführungen zu seinem "verbesserten Bubblesort" klingen auch sehr nach Insertion Sort.


    Haha - das ist ja geil. Das ist genau meine Sortierroutine! Jetzt weiß ich nach ca. 25 Jahren auch endlich, wie der Sorter heißt, den ich mir da zusammen gestrickt habe. :lol23:
    Vielen Dank Mac Bacon! Ich hätte echt nicht gedacht, dass es für das Teil einen eigenen Namen gibt. Für mich war es immer nur ein verbesserter Bubblesort. :schande:
    Aber ich hatte doch recht, dass der besser ist als der Bubblesort, oder?

    Daher die hässliche Dummy-FOR-Schleife, bei der über "f = 0" ein weiterer Durchlauf forciert wird.


    Hässlich? Ich hatte die beiden Abbruchkriterien per IF und OR abgefragt. Ich finde deine Lösung mit der Schleife viel "Eleganter" und ich wette auch, dass die schneller ist als meine Lösung.

    Klar hab' ich das.


    Sicher?

    Danach habe ich dann einige Testläufe gegen einen Quicksort gemacht.

    von der Idee kommt man aber schnell ab, wenn man mal einen laufenden Quicksort zur Hand hat und die beiden gegeneinander antreten läßt.
    ...

    Als Ergebnis: Für eine Highscoreliste bietet sich also der Bubblesort an.

    Wie geschrieben, hatte ich das alles schon gemacht. Ich habe auch nie behauptet, dass man für die Highscoreliste einen besseren Bubblesort braucht. Es ging nur um die Vor- und Nachteile der Sorter und da stellt sich halt raus, dass der Quicksort in einigen Bereichen viel schneller ist aber in einigen Bereichen auch deutlich langsamer. Und genau in den Bereichen kann man den Bubblesort auch noch ganz einfach und schnell deutlich optimieren. Für die Highscoreliste würde ich den originalen Bubblesort auch anpassen, weil man bei einem neuen Score auch nur ein Durchlauf nötig ist. Ein weiterer Durchlauf wäre einfach Zeitverschwendung.

    Apropos "Zeitverschwendung"? Das war es nicht - es war Spaß an der Sache! Bei meinem eigentlichen Programm wurde eine Messwerttabelle immer wieder um neue Werte erweitert und dann wieder neu sortiert. Von Messungen zu Messungen wurde der Anteil der unsortierten Werte also prozentual immer kleiner. Da war mein angepasster Bubblesort die "beste" Lösung (von denen, die ich getestet habe). Am Anfang wäre der Quicksort vielleicht noch schneller gewesen aber was spart man bei der Sortierung von 10 Werten. Bei 500 oder 1000 oder noch mehr wird es in Basic schon interessanter und da war der Quicksort halt unterlegen (und der normale Bubblesort auch). Dazu war das ganze nur eine private Spielerei/Zeitvertreib und es hat Spaß gemacht den Sorter für das gegebene Problem zu optimieren. Bei den Ladezeiten einer 1541 kann man zwar fragen, ob es sinnvoll ist, Zeit zu investieren, um bei jeder Sortierung ein paar Sekunden zu sparen. Eine ähnliche Frage wäre: Ist es sinnvoll heute noch am C64 zu "arbeiten"? Aus meiner Sicht war das optimieren des Sorters und das erstellen des Testprogramms eine größere Herausforderung als das eigentliche Messprogramm und hat mir viel mehr Spaß gemacht.

    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.


    Hallo? Hast du eigentlich gelesen, was ich geschrieben habe? Das habe ich alles schon hinter mir! Ich habe jedoch mit Listen von 1000 Werten getestet, beide Sorter immer mit exakt den gleichen Listen sortieren lassen und speziell mit unterschiedlich stark unsortierten Listen gearbeitet. Da waren:
    - kpl. sortierte Liste
    - kpl. falsch herum sortierte liste
    - kleinste Zahl an höchster Stelle
    - größte Zahl an niedrigster Stelle
    - kpl. zufällig erzeugte Liste
    - an 100 zufälligen stellen Zufallszahlen in eine sortierte Liste ausgetauscht (10% unsortiert)
    - das gleiche mit 20%
    - das gleiche mit 50%
    Die Listen erzeugen hat länger gedauert als die Sorter zu schreiben! ;)

    Ergebnisse hab ich ja oben schon erwähnt.

    Das Sortieren von gleichen Werten ist so genauso schnell wie bei einer bereits sortierten Liste (und ich wage zu behaupten: hier schlägt Bubblesort sogar Quicksort).


    Stimmt! Ich habe mich mal intensiver mit dem Bubblesort auseinandergesetzt und hab ihn in mehrerer Hinsicht verbessert. Nichts, was nicht jeder andere auch machen könnte - der Bubblesort lässt ja einiges an Spielraum für Verbesserungen. Danach habe ich dann einige Testläufe gegen einen Quicksort gemacht. Zu den Ergebnissen muss ich sagen, dass ich die Basic-Programme nicht auf BASIC V2 Besonderheiten optimiert habe. Ich habe also nicht kontrolliert, ob FOR-NEXT oder eine selbstgebastelte Schleife schneller sind und auch nicht, ob es kontraproduktiv ist Integer-Variablen zu benutzen, usw. . Ob einer der beiden Sorter damals mehr oder weniger davon profitiert hat, kann ich heute nicht mehr sagen.
    Bei sortierten Listen und nur leicht unsortierten Listen war mein Bubblesort im Schnitt doppelt so schnell wie der Quicksort. Das hört sich spontan ja gut an aber das war nur die eine Seite der Medaille. Bei kpl. unsortierten Listen war der Quicksort um den Faktor 100 schneller. Da ist die Freude über den selbst optimierten Bubblesort schnell verflogen.
    Als Ergebnis: Für eine Highscoreliste bietet sich also der Bubblesort an. Er ist deutlich einfacher zu verstehen und wird in diesem Fall auch schneller sein (wobei die Highscoreliste schon echt lang sein muss, um es zu merken). Wenn man aber Situationen hat, wo man vorher schon weiß, dass die Listen sehr lang und kpl. durcheinander sind, sollte man einen schnelleren Sorter wählen (oder am besten gleich Abstand von BASIC nehmen). ;)

    Wen es interessiert:
    Mein Bubblesort geht die Liste nur ein Mal durch und schiebt jeweils die Werte bis zur richtigen Position, dazu wird ein großer und nicht viele Kleine Ringtausche gemacht und nach dem Verschieben macht er bei der Ursprungsposition weiter. Für eine Highscoreliste mit immer nur einem neuen Wert, der einmal mehr oder weniger weit nach oben geschoben wird, ist der original Bubblesort aber trotzdem schneller. Man sollte sich aber vorher die Richtung des Bubblesort klar machen und wo der neue Wert zur Liste hinzugefügt wird. Wenn man das nicht beachtet, kann man sich in BASIC schnell mal ein paar längere Pausen einbauen!