...und wenn das Interpretergebiffe in einen separaten Thread ausgelagert wird, muss dieser hier nicht vor die Hunde gehen. Bisher war er nämlich größtenteils brauchbar.
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.

-
Alles anzeigen
Hallo, hier erst mal ein verbessertes schnelleres HEAP-SORT.
[...]
gosub103
[...]
gosub103
[...]
goto103Solange 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:
Code
Alles anzeigen10 n = 100:rem problem size 12 r = 5:rem number of runs 14 dim v(n):rem value array 16 rem runs 18 for ru = 1 to r 20 rem generate unsorted data 22 for i = 1 to n:v(i) = rnd(1):next 24 t = ti:rem start time 26 gosub 100:rem heapsort 28 rem show time 30 print ti - t,:next 32 print 34 end 100 rem heapsort - additional vars: l, b, i, j, v, f, d 102 l = n:b = (n / 2) + 1:for f = 0 to 1 step 0 104 if b = 1 then v = v(l):v(l) = v(1):l = l - 1:if l = 1 then v(1) = v:return:rem done! 106 if b > 1 then b = b - 1:v = v(b) 108 i = b:j = b + b:for d = 0 to 1 step 0:if j > l then v(i) = v:next f:rem next closes OUTER loop 110 if j < l then if v(j) < v(j + 1) then j = j + 1 112 if v(j) < v then j = l + 1:next:rem inner loop! 114 v(i) = v(j):i = j:j = j + j:nextDer 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:
CodeLauf 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 20952Besser 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
-
Hashes bringen imho aber die innere Ordnung durcheinander. Es bringt nichts, Zahlen nach ihrer Quersumme zu sortieren.
Dann nimmt man halt das Exponenten-Byte als Hash...

-
Da ist mein Neversort aber schneller....
...und falls die Daten schon vorsortiert sein sollten, bringt er auch bessere Ergebnisse.
-
Gibts tatsächlich keine Shellsort-Anhänger hier?
Shellsort ist interessant, mir aber für den Praxiseinsatz zu kompliziert. Wenn Insertion Sort nicht ausreicht, gehe ich direkt zum Heapsort über.
Gnome Sort aka Stupid Sort:
Benchmarks, wir wollen Benchmarks!

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

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:
Code
Alles anzeigenn = 100:rem problem size r = 5:rem number of runs dim v(n):rem value array rem runs for ru = 1 to r rem generate unsorted data for i = 1 to n:v(i) = rnd(1):next t = ti:rem start time rem sort! for i = 2 to n:v = v(i):rem outer loop iterates over unsorted values w = i:rem inner loop iterates over sorted values in reverse to find write pos for f = 1 to 1:rem flag for early exit if v(w - 1) > v then v(w) = v(w - 1):w = w - 1:if w <> 1 then f = 0 next v(w) = v:rem write to correct position next rem show time print ti - t,:next printZur 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...
