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

    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.

    Zitat

    Steht doch in Mikes Code, wie er sich bei gleichen Werten verhält - genauso wie bei bereits richtig sortierten Werten - er geht weiter in der Schleife. 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).

    Korrupte Sortierung? Nö, wenn er bei größeren Mengen Mist baut, dann weil der Rechner/das Betriebssystem/die Programmiersprache da Grenzen setzt. Aber nicht Bubblesort.

    Das mit der korrupten Sortierung war eine falsche Wiedergabe von meiner Seite. Ich habe aus "funktioniert nicht" in einer Eigeninterpretation "falsch sortiert" gemacht.

    Bzgl. Gleiche sortieren: Ich sehe jetzt, dass ein reiner Größer-Vergleich im Bubblesort reicht - logisch. Ich war gedanklich auf >= gepolt weil ohne diesen Operator mein sequenzieller Sortierer (so heißt das wohl, hab ich erfahren) gar nicht funktionieren würde. Das war einfach nur zu kurz gedacht.

    Mike's Algorithmus ist etwa 7x schneller als meiner gemessen auf 10 Werte.

    Bei mir sind es ca. 11 Sekunden, bei Mike etwa 1,5. Also eine Steigerung um 733%. Ich habe es extra mit Fließkommawerten <1 probiert, wobei meine nur zwischen 1 und 4 Stellen nach dem Komma hatten. Mike's haben alle mehr.

    Man müsste mal schauen wie Bubblesort sich verhält bei gleichen Werten in der Sortiermenge. Bei mir wird es abgefangen, egal wieviele Gleiche und an welcher Stelle. Heute hat mir ein Entwickler aus meiner Firma erzählt, Bubblesort wird irgendwann korrupt bei bestimmten Sortiermengen. Ich glaube, mein Code erzeugt keine korrupten Sortierungen, wird >10 bloß unbrauchbar langsam, z.B. in Spielen für Highscore-Listen (wobei man per Compiler sicher noch was machen könnte, so dass der Spieler nicht stutzt warum das Programm scheinbar einfriert).

    Da bis 20 aber Bubblesort kein Stress macht, sollte man diesen Algorithmus nehmen für eigene Highscore-Listen.

    Edit

    @ Oobdoo

    Ich habe meinen Sortieralgo vorhin 1:1 in WinCPC ausgeführt per Autotype. Ich war beeindruckt, der Basic-Parser des CPC übernimmt die Syntax ohne Murren und es klappt tatsächlich. Mit dem Unterschied, dass der CPC meinen Code um etwa die Hälfte schneller ausführt als der Cevi wie Du schon sagtest.

    Hallo,

    "nebenan" läuft ja ein Sortierwettbwerb in der Assembler-Ecke mit 256 Bytes. Bei der letzten Assembler-Compo ging es ums Buchstaben-Umdrehen und es gab einen funktionierenden Basic-Code dazu (an dem ich mir dann auch das Hirn zerbrochen habe).

    Diesmal ist kein Basic-Beispiel aufgeführt also dachte ich, ich schreibe eins. Sortieren braucht man doch, vor allem für Highscore-Tabellen.

    Mein Code geht, aber es ist eine Pein, weil er so langsam ist. Kann das jemand schneller?