Sortieren in V2 BASIC

Es gibt 150 Antworten in diesem Thema, welches 27.072 mal aufgerufen wurde. Der letzte Beitrag (26. Dezember 2015 um 13:42) ist von BlackJack.

  • Mal wieder was konstruktives: ich habe mich am Heapsort ausprobiert und Mikes Listing ergänzt. Grundidee beim Heapsort: es wird ein Heap gebaut (vereinfacht: hierarchische Struktur wo jedes Element max. 2 Kindelemente hat, Kindelemente sind kleiner als das Vaterelement). Dazu beginnt man beim letzten Knoten in der Hierarchie, der über Kind-Knoten verfügt und sorgt dafür, dass die Bedingung Vaterelement > Kindelement stimmt für diesen Knoten (ggf. einschließlich der weiteren Knoten, die an den Kindern hängen). Dies wiederholt man für alle Knoten. Wenn das durch ist, ist die Aufbauphase beendet...

    Anschließend wird das oberste Element weggenommen und durch das letzte Element des Heaps ersetzt. Danach wird der Heap korrigiert (damit größtes Element wieder oben steht) und danach wird wieder das oberste Element genommen. Die entnommenen Element werden am Ende der Liste angehängt (präzise und korrekt formuliert: erstes entnommene Element an letzter Stelle, zweites an vorletzter Stelle usw.) und bilden das Sortierergebnis

    Die Ausrichtung des Heaps wird im Sift-Unterprogramm durchgeführt.

    Was mich etwas betrübt: Quicksort ist durch die Bank schneller. C'est la vie. Andererseits weiß ich, dass Quicksort in der Performance auf Bubblesortniveau einbrechen kann. Das tut Heapsort nicht. Die Zahlen fortgeführt:

    Der Code:


    Variablen: en = Ende Array, rt = Vaterwurzel, ch = Kindwurzel, rs = Zwischenspeicher Vaterwurzel (um rt wiederherzustellen nach Beendigung Unterprogramm)

  • [..]

    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.
    [..]


    Im Übrigen finde ich Highscores sortieren ohnehin mit Kanonen auf Spatzen geschossen (also eigentlich keine wirkliche Aufgabe für einen Sortieralgorithmus).
    Geht man davon aus, dass die Highscore-Liste bereits sortiert ist, dann reduziert sich die Aufgabe ja auf das Einfügen eines neuen Wertes. Das Suchen der richtigen Position geht dann mit binärem Suchen in den Aufwand O(log N), das Einfügen variiert ja nach Datenstruktur von O(1) bis O(N). D.h. ein Bubble-Sort verkommt ohnehin nur zu einer Schleife, die genau einen "Bubble" (den neuen Highscore) mit im Schnitt N/2 Vertauschungen an den richtigen Platz bringt. ;)

  • Noch eine kleine Syntax-Erklärung für Anfänger die hier mitlesen zu Mike's Bubblesort-Urcode:

    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

    Basic unterscheidet zwischen Arrays und Variablen auch wenn sie denselben Namen tragen. x=x(t) hätte auch v=x(t) heißen können und x(t+1)=v statt x(t+1)=x.

    if p then 12 heißt wenn p = 0 dann 12. Man hätte auch schreiben können if p=0 then 12.

    Wenn am Ende eines Sortierdurchlaufs mindestens ein vertauschtes Wertepaar übrig bleibt wird der Sortierdurchlauf wiederholt. Am Code sieht man, dass alles was nach der if-Bedingung kommt, nicht ausgeführt wird, wenn die if-Bedingung nicht erfüllt ist - inklusive aller Befehle die durch Doppelpunkte aneinander gereiht sind.

    Ich selber schreibe immer noch viel "naiven" Code, d.h. ohne Kürzel, die dem Interpreter Arbeit abnehmen. Da dachte ich es schadet nicht das kurz auszuführen falls man an der Syntax hängt und gar nicht bis zum Konzept dahinter durchkommt.

  • Hallo Leute,

    ich muss sagen, dieser Thread ist mal wieder total interessant! Macht bloß weiter und zeigt mir noch mehr Sortier-Möglichkeiten. Das ist total spannend. :dafuer:


    Liebe Grüße!
    ThomBraxton

  • if p then 12 heißt wenn p = 0 dann 12. Man hätte auch schreiben können if p=0 then 12.


    Nein, das heißt genau das Gegenteil: if p then 12 bedeutet: if p <> 0 then 12
    Im CommodoreBasic steht 0 für "false" und jeder andere Wert für "true".

  • Noch eine kleine Syntax-Erklärung für Anfänger die hier mitlesen zu Mike's Bubblesort-Urcode:

    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


    [..]
    if p then 12 heißt wenn p = 0 dann 12. Man hätte auch schreiben können if p=0 then 12.
    [..]

    Vielleicht nur ein gedanklicher Ausrutscher, aber die Bedingung ist erfüllt, wenn p<>0 (ungleich 0) ist!
    D.h. die Ersatzschreibweise ist

    Code
    if p<>0 then12


    D.h. es wird hier sogar ganz sauber das Basic "true" (-1) verwendet, im konkreten Fall und so wie CBM-Basic das IF-THEN implementieren würde aber auch jeder Wert ungleich 0 reichen. ;)

  • ich muss sagen, dieser Thread ist mal wieder total interessant! Macht bloß weiter und zeigt mir noch mehr Sortier-Möglichkeiten. Das ist total spannend. :dafuer:

    Ok, wieso nicht - nach den komplizierten Algorithmen mal ein einfacher: Selection Sort.

    Hier wird in der Wertliste, von der ersten Position beginnend, nach dem kleinsten Wert gesucht. Ist er gefunden (was man erst weiß, wenn man alle n Elemente durch hat), wird der kleinste Wert mit dem ersten Wert in der Liste getauscht. Danach wird von der zweiten Position aus der kleinste Wert gesucht (über n-1 Elemente) und ggf. getauscht. Usw usf.

    Klingt ziemlich umständig und ineffizienter als Bubblesort, aber Selection Sort ist schneller und trotzdem leicht selbst herleitbar:

    Selection Sort ist ähnlich kompakt wie Bubble-Sort - ich hab' ihn in die Zeilen 71-74 gepackt:

  • Code
    70 rem ** selection sort 
    71 ifr<=lthenreturn 
    72 forx=ltor-1:m=x:fory=x+1tor:ifa(m)>a(y)thenm=x 
    73 next:ifm<>xthens=a(m):a(m)=a(x):a(x)=s 
    74 next:return


    Da hat sich ein Bug eingeschlichen: Es muss
    72 forx=ltor-1:m=x:fory=x+1tor:ifa(m)>a(y)thenm=y
    Sonst rutscht das gefundene Minimum nie nach unten, d.h. weil sonst x=m gilt, käme es nie zu einer Vertauschung. ;)
    Damit verlängert sich dann freilich auch die Laufzeit.

    Der Aufwand gegenüber Bubble ( (n-1)*(n-1) ) ist mit (n-1)*(n-2)/2 zumindest im Worst-Case geringer, aber es hat immer gleich viele Durchläufe, wenn auch nur n-1 Vertauschungen (bei Bubble meist viel mehr). Es profitiert damit kaum von einer Vorsortierung. Das dann praktisch, wenn
    die Vertauschungsoperation aufwändig ist oder überhaupt nicht so einfach geht (weil die Elementgröße verschieden sind). Typisch: Der Stringheap des Basic-Interpreters. Dort kommt auch quasi ein Selection-Sort zum Einsatz: Die Garbage-Collection ist genau das. Dort ist allerdings das Kriterium, jenen aktiven String mit der höchsten Adresse nach oben zu sortieren (um diesen dann über Lücken hinweg ganz nach oben zu schieben). Da sind Elementvertauschungen ala Bubble ziemlich unpraktisch (bzw. unmöglich). ;)

  • Ich muss mal schauen, ob ich den Fehler auch im angehängten Programm drin habe - bei mir waren die Ergebnisse sortiert. Irgendwie schaffe ich es immer wieder, das der Code im Notepad kleine Unterschiede zu dem in Vice hat... :schande: immerhin hab ich diesmal die Ergebnisausgabe nicht auskommentiert :whistling:

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • Ich muss mal schauen, ob ich den Fehler auch im angehängten Programm drin habe - bei mir waren die Ergebnisse sortiert. Irgendwie schaffe ich es immer wieder, das der Code im Notepad kleine Unterschiede zu dem in Vice hat... :schande: immerhin hab ich diesmal die Ergebnisausgabe nicht auskommentiert :whistling:


    Im sort4.prg war es auch ... :(

  • Hallo, Leute,

    für Fälle, wie einen Hi-Score empfehle ich "Einfueg-Sort".
    Das funktioniert wie das Einfuegen einer Karteikarte in einen Stapel.

    Code
    0 :rem---einfuegen
    9 :
    10 :forj=1to9:gosub20:next:list
    19 :
    20 :m=9::a=int(rnd(1)*m+1)::i=0
    21 :ifa>a(i+1)andi<mthen:a(i)=a(i+1):i=i+1:goto21
    22 :a(i)=a:printa":";:fori=mto1step-1:printa(i);:next:print:return

    Schönen Gruß.

  • So, hab nochmal mit dem Bugfix die Zeiten genommen. Bei 10 ist er geringfügig langsamer, aber in dem Bereich ist er immer noch schneller als Quicksort. Und Überraschung: bei 100 und mehr ist er schneller geworden!


  • Hallo, Leute,

    für Fälle, wie einen Hi-Score empfehle ich "Einfueg-Sort".
    Das funktioniert wie das Einfuegen einer Karteikarte in einen Stapel.


    Code
    0 :rem---einfuegen
    9 :
    10 :forj=1to9:gosub20:next:list
    19 :
    20 :m=9::a=int(rnd(1)*m+1)::i=0
    21 :ifa>a(i+1)andi<mthen:a(i)=a(i+1):i=i+1:goto21
    22 :a(i)=a:printa":";:fori=mto1step-1:printa(i);:next:print:return

    Coole Idee, bastel ich doch gleich mal in das Programm rein, mit Anpassung für den Arraybereich von 0 bis 10:


    Array b brauche ich, damit das Ergebnis nachher Stück für Stück in ein leeres Array a reingesetzt werden kann. Der Fairness halber wird die Zeitmessung auch erst danach gestartet. Ansonsten dürfte ich das Wesen des Ausgangscodes gut aufgegriffen haben.

    Was sagen die Zahlen?

    Code
    Einfueg-Sort
    
    
       N  Lauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5
    
    
      10    131    148    137    122    142
     100  10810  10390  11146  10675  10970
    1000  nicht getestet

    Ich glaub', ich bleib da lieber bei nem anderen Sort... obwohl, bei N=10 hat er fast QuickHeapsort-Niveau.

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • Tale-X:
    Besten Dank, hier noch ein paar Verbesserungen.

    Falls das Sortierfeld größer als m=9 ist muß man natürlich mit dima(m+1) ein Feld anlegen.

    Code
    0 :rem---einfuegen
    9 :
    10 :dima,i,j:m=9:a(m+1)=1e3::forj=1to9:gosub20:next:list
    19 :
    20 :a=int(rnd(1)*m+1)::i=.
    21 :ifa>a(i+1)then:a(i)=a(i+1):i=i+1:goto21
    22 :a(i)=a:printa":";:fori=mto1step-1:printa(i);:next:print:return

    Schönen Gruß.

  • Ich hab mal die groben Kanten geglättet und die Speicherverschwendung minimiert:

    Code
    0 :rem---einfuegen
    8 :
    9 input"anzahl werte:";m:ifm<1orm>11thenprint"bitte werte von 1 bis 11":goto9
    10 :dima(m-1)::forj=0tom-1:gosub20:next:list
    19 :
    20 :a=int(rnd(1)*m+1)::i=0
    21 :ifi<m-1then:ifa>a(i+1)then:a(i)=a(i+1):i=i+1:goto21
    22 :a(i)=a:printa":";:fori=m-1to0step-1:printa(i);:next:print:return

    Wissen ist das einzige Gut, das sich beim Teilen vermehrt. Also seid vorsichtig damit!

  • 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


  • ...
    Coole Idee, bastel ich doch gleich mal in das Programm rein, mit Anpassung für den Arraybereich von 0 bis 10:

    Was daran "cool" entzieht sich meiner Wahrnehmung. Das Einsortieren eines Wertes in einen sortierten Stapel ist in der linearen Implementierung auch nicht anders machbar. Wenn wenigstens das Einsortieren per binärer Suche vorgestellt worden wäre, aber selbst das gehört zu den nicht erwähnenswerten Standardalgorithmen in der Informatik.
    Das hat ja wirklich erstmal nichts mit Sortieren an sich nichts zu tun, außer das die Einfügeoperation von der Sortierung des "Stapels" profitiert.
    Der eigentliche Sortieralgorithmus hat dann in der Tat Tale-X zusammengebastelt ... also eigentlich Tale-X'es Einfueg-Sort!


    Array b brauche ich, damit das Ergebnis nachher Stück für Stück in ein leeres Array a reingesetzt werden kann. Der Fairness halber wird die Zeitmessung auch erst danach gestartet. Ansonsten dürfte ich das Wesen des Ausgangscodes gut aufgegriffen haben.


    Das Sortieren geht in dieser Form leider von recht vielen Voraussetzungen aus und macht mehr als notwendig.

    • Stillschweigend wird ein Minimum von 0 vorausgesetzt. D.h. die zu sortierenden Werte müssen >=0 sein.
    • Der Stapel, in den einsortiert wird, umfasst hier von Beginn immer mit N Elemente und muss daher mit "Minimumwerten" vorgefüllt sein. Es reicht hier den Stapel nach und nach aufzufüllen.
    • Unfairerweise ist die "innere" Schleife eine GOTO-Schleife (mit bekanntem schlechten Laufzeitverhalten) und daher zumindest im Vergleich zum Selection-Sort, wo FOR-NEXT in der inneren Schleife seine Vorteile ausspielt.


    Bei 6 Elementen:
    b12345 a12345
    654321 000000
    654321 000006
    654321 000056
    654321 000456
    654321 003456
    654321 023456
    654321 123456

    Hier sieht man, dass von Beginn an die Werte (die Nullen) von "vorne" durchgeschoben werden, nur damit die größeren Werte ans Ende des Arrays einsortiert werden. Eine sehr ungünstige Grundinitialisierung für den Stapel.

    Was sagen die Zahlen?

    Code
    Einfueg-Sort
    
    
       N  Lauf 1 Lauf 2 Lauf 3 Lauf 4 Lauf 5
    
    
      10    131    148    137    122    142
     100  10810  10390  11146  10675  10970
    1000  nicht getestet

    Ich glaub', ich bleib da lieber bei nem anderen Sort... obwohl, bei N=10 hat er fast QuickHeapsort-Niveau.

    Ein von mir korrigierte Variante zeigt sich da schon freundlicher (dabei mit der Initialisierung von B() gemessen!):

    Code
    N  Lauf 1  Lauf 2  Lauf 3  Lauf 4  Lauf 5
    
    
      10      36      38      52      45      47
     100    2516    2184    2394    2125    2505
    1000  225843  221826  223335 .....

    Also bei N=10 unter Quicksort- und sogar Selection-Sort-Niveau.
    Auch bei 100 noch auf Heap-Sort-Niveau, aber immer wieder deutliche Schwankungen.
    Bei 1000 noch immer unter Selection-Sort, aber als quadratischer Algorithmus gegenüber den logarithmischen dann schon deutlich hinten.
    Unter der Voraussetzung, dass hier noch ein 2. Array gleicher Größe gebraucht wird, schränkt sich der Gebrauch dieser Variante ziemlich ein.

    Als Fleißaufgabe, kann man das Stapeleinsortieren mit binärer Suche machen und müsste dann in die Region von Quicksort und Heap-Sort kommen (Aufwand O(N*logN)). Das sei dem geneigten Leser überlassen. ;)

    Meine Variante (mit linearem Einfügen) sieht nun so aus:

    Code
    30 dimb(n):fori=0ton:b(i)=a(i):next:t1=t1:rem startzeit korrigieren
       31 fort=1ton:a=b(t)
       32 fori=t-1to.step-1:ifa>=a(i)then34
       33 a(i+1)=a(i):next
       34 a(i+1)=a:next t:return


    Einige Bemerkungen dazu:

    • Gültig für n>=1 (also ab 2 Elementen).
    • Die Zeitnehmung beginnt also schon vorher, regulär (die T1-Zuweisung ist nur ein Dummy).
    • Es braucht kein Minimum angelegt werden - a() enthält wir schrittweise aufgebaut, nur a(0) wird initial übernommen (auch wenn alle weiteren Elemente unverändert bleiben, sie werden jedoch der Reihe nach überschrieben).
    • Das Verlassen der inneren FOR-NEXT-Schleife beim NEXT endet mit dem Wert -1 in i.
    • Die innere Schleife ist nun ein FOR-NEXT (also vergleichbar mit Selection-Sort)
    • Der Abbruch der inneren Schleife in Zeile 32 mit Sprung auf Z. 34 ist kein Problem, da NEXT T (mit expliziter Laufvariable) die offene innere Schleife beseitigt! Also keine Ausnutzung eines zufälligen Verhaltens, sondern eine reguläre Eigenschaft des Interpreters.


    Sortierablauf für 6 Elemente:
    b12345 a12345
    6(5)4321 6XXXXX
    65(4)321 56XXXX
    654(3)21 456XXX
    6543(2)1 3456XX
    65432(1) 23456X
    654321() 123456

    X sind nicht verwendet, Wert in () wird einsortiert.

  • Also in PostBitte melde dich an, um diesen Link zu sehen. wird vor allem das Sortieren von Hiscore-Tabellen angesprochen.
    Und mein Beitrag stellt eine Sortierlösung für Hi-Score-Tabellen vor.
    In gewisser Weise der Hi-Score in zwei Basic-Zeilen.

    Die Einfüg-Zeit hängt immer von der Position des eingefügten Elements ab.

    Schönen Gruß.