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

    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.

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

    Tale-X:

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

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

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

    Als nächstes folgt ein schnelleres EINFÜG-SORT:

    Das hab ich mal vor Jahren programmiert.


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

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

    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.

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