...
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!
rem ...
13 t1=ti:l=0:r=n:gosub30:t2=ti
rem ...
28 :
29 rem ** biffs-einfueg-sort
30 dimb(n):forx=0ton:b(x)=a(x):a(x)=0:next:t1=ti:rem startzeit korrigieren
31 :fort=0ton::a=b(t)::i=0
32 :ifi<nthen:ifa>a(i+1)then:a(i)=a(i+1):i=i+1:goto32
33 :a(i)=a:next:return
48 :
49 rem ** quick-sort
Alles anzeigen
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?
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!):
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:
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.