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

    ich grübel gerade über den Abschnitt b = (n / 2) + 1 in Zeile 100. Funktioniert das so zuverlässig oder sollte da nicht lieber b=int(n/2)+1 stehen? Bei n=1 ergibt sich b=1.5 und erfüllt in Zeile 104 nicht die if-Bedingung.

    Gut aufgepasst, da hab ich Mist gebaut. Ich hab an der Stelle ganz verschwitzt, dass die Variable in Basic2 ja ein Float ist.

    Der Einfüg-Sort-Plus Algorithmus ist übrigens sogar schneller als Heap-Sort.

    Nein, ist er nicht. Deine Implementation ist bis zu einer gewissen Problemgröße schneller, weil ein Teil der Arbeit von einer Maschinensprache-Unterroutine erledigt wird. Für den Algorithmus ist das uninteressant, der hat trotzdem eine schlechtere Komplexitätsklasse.

    ...und jetzt ist auch dieser Thread im Eimer. :whistling:

    Solange der Sift-Down-Teil jedes Mal per GOSUB angesprungen wird, ist da nichts zu holen. Man kann Heapsort aber auch innerhalb einer einzigen Schleife abfrühstücken:

    Der Sort-Aufruf per GOSUB erlaubt den Aussprung aus den geschachtelten Schleifen (RETURN räumt sie vom Stack), und in Zeile 108 benutze ich Mikes Vorschlag, per expliziter Variablenangabe bei NEXT gleich die äußere Schleife zu schließen.

    Benchmarks:

    Code
    Lauf 1  Lauf 2  Lauf 3  Lauf 4  Lauf 5
    n=10:      72      70      73      69      71
    n=100:   1407    1415    1411    1387    1434
    n=1000:	20984   20981   20923   20940   20952

    Besser als die Variante aus Bitte melde dich an, um diesen Link zu sehen., aber immer noch weit entfernt von Quicksort. Letzteren kann man wohl erst bei Problemgrößen schlagen, die in Basic2 nicht machbar sind.

    EDIT: Link eingefügt und Programm angehängt

    Hier noch eine Einfüg-Sort-Variante:

    ...die immer noch nicht in der Lage ist, den Wert Null korrekt einzusortieren, da sie immer noch von nicht erwähnten Nebenbedingungen ausgeht. In bestimmten Einsatzfällen mögen die Beschränkungen akzeptabel sein, aber sie hier zu verschweigen, hilft niemandem.

    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?

    Ja. Immer.

    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.

    Ja, aber "schön" wäre es, wenn man in Basic2 gar nicht erst zu solchen Tricks greifen müsste. Die Schlüsselwörter DO, LOOP und EXIT ab Basic 3.5 halte ich daher für sehr viel wichtiger als die ganzen Grafik/Sound/Disk-Anweisungen.

    Hatten wird doch schon schon alles, siehe Bitte melde dich an, um diesen Link zu sehen. ... oder? ;)

    Ja, mit einem zweiten (unnötigen) Array, basierend auf dem BIF-Unfall und ohne den Standardnamen zu erwähnen. ;)

    Da in diesem Thread so oft der Bubble Sort erwähnt wurde, konnte ich nicht anders und hab hier zum Vergleich einen Insertion Sort gebaut:

    Zur Erklärung: Selbst unter den naiven Sortieralgorithmen mit Komplexität O(n²) gilt der Bubble Sort eigentlich als das Standardbeispiel für einen schlechten Sortieralgorithmus, z.B. wegen der vielen unnötigen Schreibzugriffe auf das Array. Insertion Sort ist auch nicht schwieriger zu verstehen, aber immer schneller in der Ausführung. Ich nehme an, dass BIFs Programm eigentlich ein Insertion Sort sein/werden sollte, und Cyberdynes Ausführungen zu seinem "verbesserten Bubblesort" klingen auch sehr nach Insertion Sort.

    Die Funktionsweise: Man unterteilt das Array gedanklich in einen sortierten und einen unsortierten Teil. Am Anfang umfasst der sortierte Teil einfach das erste Element und der unsortierte den Rest.
    Die äußere Schleife iteriert nun von 2 bis N und sortiert dieses Element in den bereits sortierten Teil ein. Dies geschieht, indem in der inneren Schleife so viele Werte um eine Position verschoben werden, bis die korrekte Position für den einzusortierenden Wert gefunden ist.
    Die erwähnte Funktionalität des Einsortierens einer Punktzahl in eine Highscoreliste entspricht also einem einzigen Durchlauf durch die innere Schleife. Der Gesamtalgorithmus besteht somit quasi nur daraus, mit einem einzigen Highscore anzufangen und dann alle anderen Werte nacheinander in die wachsende Liste einzusortieren.
    Schwer verständlich an obigem Programm ist nur die innere Schleife, da Basic2 nur FOR-Schleifen kennt und es zwei verschiedene Möglichkeiten gibt, die Schleife zu verlassen:
    Entweder der Vergleich "v(w - 1) > v" ist FALSE, dann ist die korrekte Einfügeposition gefunden.
    Oder nach "w = w - 1" hat w den Wert 1, dann gibt es keine Werte mehr zum Vergleichen.
    Daher die hässliche Dummy-FOR-Schleife, bei der über "f = 0" ein weiterer Durchlauf forciert wird.

    Ich hoffe, ich habe in dem Programm jetzt keine peinlichen Fehler eingebaut; ich hab es nicht allzusehr getestet... :whistling: