Dafür ist meine Variante etwas kürzer, bei ungefähr gleicher Leistung.
Schönen Gruß.
Dafür ist meine Variante etwas kürzer, bei ungefähr gleicher Leistung.
Schönen Gruß.
Hallo Leute, ich hab hier noch mal eine neue Heap-Sort-Variante.
Die im Vergleich zu dem ersten Heapsort im Thread 1/3 Zeitersparniss bringt.
Heap-Sort-22, weil es in etwa 22 Sekunden für 100 Strings benötigt.
Damit kann Heapsort dann durchaus mit Quicksort mithalten.
300 :rem----heap-sort-22
301 :e=n-1:fori=int(e/2)to.step-1:a=i:gosub305:next
302 :fore=eto.step-1:a=.:b=a(e+1):a(e+1)=a(a):a(a)=b:onsgn(e)gosub305:next:return
305 :forc=a+a+1toe:ifa(c)<a(c+1)then:c=c-(c<e)
306 :ifa(a)<a(c)then:b=a(a):a(a)=a(c):a(c)=b:a=c:c=a+a:next
307 :return
Schönen Gruß.
Es sind die Speicherstellen 71/72 .
Ob das bei anderen Computern ähnlich funktioniert weiß ich allerdings nicht.
Beim C64 funkt es allerdings ganz gut.
Ansonsten müßte man wohl die Variablenadresse komplizierter errechnen.
Schönen Gruß.
Bubble-Sort basiert im Prinzip auf dem Nachbar-Tausch Verfahren.
Also ein größerer Nachbar tauscht mit einem kleineren Nachbarn, wenn der über ihm steht.
Und wenn man das n Mal laufen lässt, ergibt sich dann eine sortierte Folge.
Schönen Gruß.
oobdoo:
Als erstes solltest du die Variablen mit :dim v,a$: anlegen.
Und statt *h solltest du mal *256 nehmen, falls h=256 noch nicht definiert wurde.
Schönen Gruß.
@TaleX:
Kann sein. Das müßte man dann noch korrigieren.
Schönen Gruß.
Ausprobieren.
Im übrigen ist Einfüg-Sort-Plus wohl vielseitiger als Quicksort.
Da es schneller einfügt und sortierte Felder schneller erkennt.
Bei einem Test mit einem 2D-String-Feld, 150 Strings kommt es bei mir sogar an die Q-Sort Geschwindigkeit ran.
Schönen Gruß.
Mit Tricks kann man auch in Basic.V2 schon viele Dinge machen, die es standard-mäßig erst in höheren Versionen gibt.
Das ist relativ sicher den Zeiger so zu ermitteln. Man sollte die Variablen nur vorher mit :dim a$,v: angelegt haben.
Und schon klappt es.
Der Einfüg-Sort-Plus Algorithmus ist übrigens sogar schneller als Heap-Sort.
Getestet mit 100 Feldvariablen.
Bei Mehrdimensionalen Feldern kann man einfach die Kopierdistanz d anpassen.
Und schon wird alles mitkopiert.
Schönen Gruß.
@stefan:
Genau so funktioniert es.
Das geht überigens auch mit String-Variablen.
:v=0*len(a$)+peek(71)+peek(72)*256:
Die Adresse der zuletzt benutzten Variable steht in 71/72.
Schönen Gruß.
Also ohne Erklärug kann es manchmal schwierig werden.
Bzw. sich in andere Programme hineinzudenken ist wohl nie ganz leicht, da man natürlich nicht weiß, was bezweckt werden soll.
Aber im Prinzip alles ganz logisch.
Schönen Gruß.
Tale-X:
Ah ja, damit berechnet man die Variablenadresse.
Und in der Variablen d wird die Kopier-Distanz angegeben.
Hier 5 Byte für 1 x Fließkomma-Variable.
Schönen Gruß.
Als nächstes folgt ein schnelleres EINFÜG-SORT:
Das hab ich mal vor Jahren programmiert.
200 :j=1:rem---einfueg-sort-plus(j,n)
201 :dima,b,c,d,e,n,h,v,i,j,k:h=256
202 :d=5:v=0*a(.)+peek(71)+peek(72)*h
203 :forj=jton:ifa(j)>=a(j-1)then:next:return
204 :b=(1+j)/2-1:i=1+b:k=a(j)
205 :fori=ito.step.:b=b/2:c=((a(i-1)>k)-(a(i)<k))*b:i=i+c:ifcthennext
206 :i=int(i):a=v+d*i:e=v+d*j-1:n=a+d
207 :b=e-a:c=int(b/h)*h:poke781,c/h+1:poke782,b-c+1and255:b=a+c:poke91,b/h
208 :poke90,b-peek(91)*h:b=n+c:poke89,b/h:poke88,b-peek(89)*h:sys41964
209 :a(i)=k:nextj:return
Das ganze funktioniert als Einfüg-Sort mit einem binärem Such-Algorithmus (202-203),
danach werden die Adressen im Variablenfeld berechnet(206) und
mit dem Basic internem Kopierprogramm(207-208) die Variablen verschoben.
Das Einfügen erfolgt dann in Zeile 209.
Schönen Gruß.
Hallo, hier erst mal ein verbessertes schnelleres HEAP-SORT.
Basierend auf den hier im Thread veröffentlichten Algorithmus.
100 :rem---heap-sort
101 :en=n-1:forrs=int(en/2)to.step-1:rt=rs:gosub103:next
102 :foren=ento.step-1:rt=.:s=a(en+1):a(en+1)=a(.):a(.)=s:gosub103:next:return
103 :ch=rt+rt+1:ifch<enthen:ifa(ch)<a(ch+1)then:ch=ch+1
104 :ifch<=enthen:ifa(rt)<a(ch)then:s=a(rt):a(rt)=a(ch):a(ch)=s:rt=ch:goto103
105 :return
Schönen Gruß.
Ich hab mir den Film mit den Sortieralgorithmen gleich zweimal angesehen.
Sehr interessant und anschaulich gemacht.
Sortier-Programme sind ja ein interessantes Programmierfeld, bei dem man manche Stunde verbringen kann.
Und der Thread hat ja sogar zu zwei oder drei schnelleren Sortier-Programmen geführt.
Da mußte ich gar nicht mal beweisen, daß es ein schnelleres Einfüg-Sort oder Selection-Sort gibt.
Schönen Gruß.
In einfachen Fällen ist Registrierung schon fast Sortierung.
In jedem Fall ist es eine Art Vorsortierung.
Schönen Gruß.
Bucket-Sort hat aber den Nachteil, daß es keine Strinxen sortieren kann.
Für Numerix ist das aber scheinbar unschlagbar.
Schönen Gruß.
Ich hab Shell-Sort mal abgetippt und bin positiv überrascht.
Bei genauem Hingucken kann man sogar noch das if GOTO durch if then ersetzen.
Dann kommt SHELL-Sort sogar ohne Sprünge aus, was das ganze noch etwas schneller machen sollte.
497 :
498 rem shell-sort
499 :
500 ford=nto1step0
510 d=int(d/2)
520 fori=0ton-d
530 s=a(i+d):forj=ito0step-d
540 ifa(j)>sthen:a(j+d)=a(j):next
560 a(j+d)=s:nexti:next:return
Schönen Gruß.
Ist Bubblesort gleich Einfüg-Sort ?
Nun bei Bubble-Sort ist die Frage, welches Konzept da überhaupt verfolgt wurde.
Der Name sagt, daß da Blasen(bubbles), wie in einem Reagenzglas, nach oben steigen sollen.
Das ist für´s Sortieren ein eher konfuses System, vermutlich von einem Chemiker programmiert.
Also wenn Bubble-Sort auf einen größeren String trifft, wird der größere String nach oben durchgetauscht.
Theoretisch könnte man da eine Mischung von Selektion-Sort und Einfüg-Sort drin sehen.
Schönen Gruß.
Ich hab das Einfüg-Sort genannt, weil das Grundprinzip dem Einfügen einer Kartei-Karte entspricht.
Vermutlich das Urprinzip des Sortierens überhaupt.
Schönen Gruß.