QUICKSORT ...es funktioniert nicht... wer hilft mir ?

Gerhard · Beitrag von **Gerhard** » 03.12.2004 21:50

Hallo,
muss meine mehr als 16000 QSOs wohl oder übel mit
QUICKSORT sortieren, da es bei Bubblesort ca. 4 Minuten
dauert. Jetzt habe ich mir aus der Liga PureBASIC einen
QUICKSORT Algorithmus heruntergeladen und einen Test
gemacht. Ein Random Generator erzeugt z.B. 10 beliebige
Zahlen und diese sollten vom QUICKSORT sortiert werden!
Das funktioniert aber nicht. QUICKSORT arbeitet zwar,
aber es erfolgt keine richtige Sortierung...
Was mache ich da noch falsch,
denn der QUICKSORT Quelltext wurde ja so vorgegeben!
Wer weiss woran es liegt, dem wäre ich sehr dankbar.

Hier der Quelltext:

Code: Alles auswählen

;------QUICKSORT-------------

Dim zahlen(10)
anzahl = 10
OpenConsole()

PrintN("ORIGINALZAHLEN:")

For i=0 To anzahl
    zahlen(i)=Random(100)
    Print(Str(zahlen(i))+" ")
    
Next i
PrintN("")


l = 0 
r = 10

qsort: 
    i = l 
    j = r 
    pivot = zahlen(l)

    While (i<=j) 
        While zahlen(i) < pivot: i=i+1: Wend 
        While zahlen(j) > pivot: j=j-1: Wend 
   

        If (i<=j) 
            
            temp=zahlen(i) : zahlen(i)=zahlen(j) : zahlen(j)=temp
            i=i+1 
            j=j-1 
            
        EndIf 
        
    Wend 
    If (l<j) : r=j : Goto qsort : EndIf 
    If (i<r) : l=i : Goto qsort : EndIf 

PrintN("ZAHLEN SORTIERT:")

For i = 0 To anzahl
     Print(Str(zahlen(i))+" ")

Next i
PrintN("")
Print("FERTIG")
Input() 
CloseConsole() 
End
;-------------------------------------------------

Gruss
Gerhard

edit redacid: codetags gesetzt.

ChaOsKid · Beitrag von **ChaOsKid** » 04.12.2004 09:19

hi Gerhard,

ich hab leider keinen plan woran es liegt
QSOs sagt mir leider auch nix...
aber warum benutz du nicht SortArray() ?
zb so:

Code: Alles auswählen

OpenConsole()
PrintN("ORIGINALZAHLEN:")
Anzahl = 10
Dim zahlen(Anzahl)
For i=0 To Anzahl
  zahlen(i)=Random(100)
  Print(Str(zahlen(i))+" ")
Next i
PrintN("")

SortArray(zahlen(),0) ;<--- hier

PrintN("ZAHLEN SORTIERT:")

For i = 0 To Anzahl
  Print(Str(zahlen(i))+" ")
Next i

PrintN("")
Print("FERTIG")
Input()
CloseConsole()
End
;--

mfG
Tobi

Gerhard · Beitrag von **Gerhard** » 04.12.2004 10:28

Hallo Tobi,
danke für die Zuschrift,jedes QSO ist einfach gesagt
ein einziger String, dass heisst, ich habe ca. 16000 Strings
zu sortieren. Tja und das will ich mit QUICKSORT
machen, aber offensichtlich gibts da noch Probleme. Man kann
also nicht einfach den Algorithmus kopieren und laufen lassen
Hmmm, wäre dankbar, wenn mir jemand sagen kann,
warum QUICKSORT es hier in meinem Beispiel nicht schafft,
10 Zahlen richtig zu sortieren.
mfG
Gerhard

Beitrag von **NicTheQuick** » 04.12.2004 13:53

Dieser Code aus dem Code-Archiv ist schon falsch. Du hast also nichts falsch gemacht von der Anwendung des Codes her.

@André: Entweder sollte der Autor seinen Code verbessern oder man sollte ihn aus dem Code-Archiv entfernen. Weil Codes, die nicht richtig funktionieren, sollten da nicht drin sein.

Ich habe jetzt gerade mal den anderen Code benutzt. Der funktioniert genauso schlecht.

Code: Alles auswählen

;------QUICKSORT-------------

anzahl = 10
Dim feld(anzahl)

OpenConsole()

PrintN("ORIGINALZAHLEN:")

For i = 0 To anzahl
    feld(i) = Random(100)
    Print(Str(feld(i)) + " ")
Next i
PrintN("")

Procedure quicksort(s, e)
  i = s
  j = e
  Repeat
    a = i + j
    While feld(i) < feld(a / 2)     ; original code ".... < feld((i+j)/2)" must be splitted because of a "Too complex...." error
      i = i + 1
    Wend
    
    While feld(j) > feld(a / 2)
      j = j - 1
    Wend
    
    If i <= j
      tmp = feld(i)
      feld(i) = feld(j)
      feld(j) = tmp
      i = i + 1
      j = j - 1
    EndIf
  Until i > j
  If j > s  :  quicksort(s, j)  : EndIf
  If i < e  :  quicksort(i, e)  : EndIf
EndProcedure

quicksort(0, anzahl)

PrintN("ZAHLEN SORTIERT:")

For i = 0 To anzahl
  Print(Str(feld(i)) + " ")
Next i

PrintN("")
Print("FERTIG")
Input()

CloseConsole()

End

Wenn man jetzt statt [c]quicksort(0, anzahl)[/c] einfach [c]SortArray(feld(), 0)[/c] benutzt, funktioniert der Code allerdings einwandfrei.

Beitrag von **Falko** » 04.12.2004 16:48

NicTheQuick hat geschrieben:Dieser Code aus dem Code-Archiv ist schon falsch. Du hast also nichts falsch gemacht von der Anwendung des Codes her.

@André: Entweder sollte der Autor seinen Code verbessern oder man sollte ihn aus dem Code-Archiv entfernen. Weil Codes, die nicht richtig funktionieren, sollten da nicht drin sein.

Ich habe jetzt gerade mal den anderen Code benutzt. Der funktioniert genauso schlecht.
Code: Alles auswählen
;------QUICKSORT-------------

anzahl = 10
Dim feld(anzahl)

OpenConsole()

PrintN("ORIGINALZAHLEN:")

For i = 0 To anzahl
    feld(i) = Random(100)
    Print(Str(feld(i)) + " ")
Next i
PrintN("")

Procedure quicksort(s, e)
  i = s
  j = e
  Repeat
    a = i + j
    While feld(i) < feld(a / 2)     ; original code ".... < feld((i+j)/2)" must be splitted because of a "Too complex...." error
      i = i + 1
    Wend
    
    While feld(j) > feld(a / 2)
      j = j - 1
    Wend
    
    If i <= j
      tmp = feld(i)
      feld(i) = feld(j)
      feld(j) = tmp
      i = i + 1
      j = j - 1
    EndIf
  Until i > j
  If j > s  :  quicksort(s, j)  : EndIf
  If i < e  :  quicksort(i, e)  : EndIf
EndProcedure

quicksort(0, anzahl)

PrintN("ZAHLEN SORTIERT:")

For i = 0 To anzahl
  Print(Str(feld(i)) + " ")
Next i

PrintN("")
Print("FERTIG")
Input()

CloseConsole()

End
Wenn man jetzt statt [c]quicksort(0, anzahl)[/c] einfach [c]SortArray(feld(), 0)[/c] benutzt, funktioniert der Code allerdings einwandfrei.

Hatte auch den code ausprobiert und meinte es funktioniert wenn ich
" Until i >= j" ändere. Habe auch 5 mal den Source laufen lassen und die Zahlen wurden richtig sortiert. Habe es jetzt nochmal Probiert und einige
Zahlen stimmten dann doch nicht mehr. Ich wage zu behaupten, das es
evt. an PB liegen muss. Dieser Qicksortalgo ist ähnlich wie der in GFA-Basic
und daher verstehe ich leider auch nicht mehr, was daran falsch sein soll.

MfG Falko

remi_meier · Beitrag von **remi_meier** » 04.12.2004 17:15

Vielleicht will jemand diesen Code von mir anpassen?

Code: Alles auswählen

#N=10
Dim a(#N)

Procedure quicksort(l,r)
  v.l
  t.l
  i.l
  j.l
  If r>l
    v=a(r)
    i=l-1
    j=r
    Repeat
      Repeat
        i+1
      Until a(i)>=v
      Repeat
        j-1
      Until a(j)<=v
      t=a(i)
      a(i)=a(j)
      a(j)=t
    Until j<=i
    a(j)=a(i)
    a(i)=a(r)
    a(r)=t
    quicksort(l,i-1)
    quicksort(i+1,r)
  EndIf
EndProcedure




Restore daten
For z=1 To #N
  Read a(z)
  k.s+Str(a(z))+" "
Next
Debug k
k=""

quicksort(1,#N)


For z=1 To #N
  k.s+Str(a(z))+" "
Next
Debug k


DataSection
  daten:
    Data.l 5,1,3,9,2,4,6,8,7,0
EndDataSection

Froggerprogger · Beitrag von **Froggerprogger** » 04.12.2004 18:04

Alternativ hier ein Link zu einer fertigen Prozedur, welche ebenfalls den Quicksort implementiert und auch mit Strings oder Callbackfunktion läuft:

http://www.robsite.de/php/pureboard-arc ... php?t=4730

Beitrag von **Falko** » 04.12.2004 20:18

remi_meier hat geschrieben:Vielleicht will jemand diesen Code von mir anpassen?
Code: Alles auswählen
#N=10...

@remi_meier
Jo, das funzt. Hatte zwar noch ein Quicksort in GFA_basic, welches prima
läuft, aber dazu benötige ich einen swap-befehl, welcher zwei Arrays tauscht. Leider ist PB noch nicht soweit!

@Gerhard, ich glaube so wolltest du es haben.
;Coder RemiMeier
OpenConsole()

Code: Alles auswählen

OpenConsole()
#N=10 
Dim SortmeF(#N) 

Procedure quicksort(l,r) 
  v.l 
  t.l 
  i.l 
  j.l 
  If r>l 
    v=SortmeF(r) 
    i=l-1 
    j=r 
    Repeat 
      Repeat 
        i+1 
      Until SortmeF(i)>=v 
      Repeat 
        j-1 
      Until SortmeF(j)<=v 
      t=SortmeF(i) 
      SortmeF(i)=SortmeF(j) 
      SortmeF(j)=t 
    Until j<=i 
    SortmeF(j)=SortmeF(i) 
    SortmeF(i)=SortmeF(r) 
    SortmeF(r)=t 
    quicksort(l,i-1) 
    quicksort(i+1,r) 
  EndIf 
EndProcedure 

; Hauptprogramm

PrintN("before sorting...") 
For i=1 To 10
SortmeF(i)=Random(500) 
Print(Str(SortmeF(i))+" ") 
Next i 
PrintN("") 
PrintN("Sortme after sorting...") 
l = 1 
r = 10 
quicksort(l,r)

For i=1 To 10
Print(Str(SortmeF(i))+" ") 
Next i

Input()

Falls hier jemand noch GFA-Basic besitzt, nochmal der Source in GFA-Basic. Habe zwar versucht das in PB zu konvertieren, aber vermutlich wegen dem fehlenden ARRAY-Swap leider nicht hinbekommen.
DIM feld&(10)

Code: Alles auswählen

//GFA-Basic
FULLW #1
PRINT "before sorting..."
FOR i& = 0 TO 9
  feld&(i&) = RANDOM(500)
  PRINT feld&(i&);" ";
NEXT i&
PRINT ;""
PRINT ;"after sorting..."
l = 0
r = 9
@quicksort(l,r)

FOR i& = 0 TO 9
  PRINT feld&(i&);" ";
NEXT i&

DO
  SLEEP
LOOP UNTIL _Mess = WM_KEYDOWN OR MENU(1) = 4
CLOSEW #1

PROCEDURE quicksort(anfang&,ende&)
  LOCAL zl&,zr&
  zentrum& = anfang&
  zl& = anfang&
  zr& = ende&
  REPEAT
    IF feld&(zl&) >= feld&(zr&)
      SWAP feld&(zl&),feld&(zr&)
      zentrum& = zl& + zr& - zentrum&
    ENDIF
    IF zentrum& = zl&
      DEC zr&
    ELSE
      INC zl&
    ENDIF
  UNTIL zl& = zr&
  IF anfang& < zl& - 1 THEN @quicksort(anfang&,zl& - 1)
  IF ende& > zr& + 1 THEN @quicksort(zr& + 1,ende&)
RETURN
//Code ends

mfg Falko

Andre · Beitrag von **Andre** » 04.12.2004 23:08

@Nic: mit dem alten Code im CodeArchiv austauschen, werde ich beim Update mit berücksichtigen.

Beitrag von **Falko** » 04.12.2004 23:56

Habs jetzt auch mit dem Swap() hinbekommen und den obigen GFA-Source endlich in PB hinbekommen.

Code: Alles auswählen

;Portiert von GFA-BASIC NACH PB
;von Falko
;InlineASM-Unterstützung bitte einschalten
;
OpenConsole()
Anzahl=10
Dim SortmeF(Anzahl) 
Dim temp(1)
;
Procedure SWAP(index1,index2)
 ;Shared SortmeF
 temp(1)=SortmeF(index1)
 SortmeF(index1)=SortmeF(index2)
 SortmeF(index2)=temp(1)
EndProcedure
;
Procedure quicksort(anfang,ende)
  ;Shared zl.l,zr.l
  zentrum = anfang
  zl = anfang
  zr = ende
  Repeat
    If SortmeF(zl) >= SortmeF(zr)
      SWAP(zl,zr)
      zentrum = zl + zr - zentrum
    EndIf
    If zentrum = zl
      DEC zr
    Else
      INC zl
    EndIf
  Until zl = zr
  If anfang < zl - 1 : quicksort(anfang,zl - 1):EndIf
  If ende > zr + 1 : quicksort(zr + 1,ende):EndIf
EndProcedure


; Hauptprogram 

PrintN("before sorting...") 
For i=1 To Anzahl 
SortmeF(i)=Random(500) 
Print(Str(SortmeF(i))+" ") 
Next i 
PrintN("") 
PrintN("Sortme after sorting...") 
l = 1 
r = Anzahl
quicksort(l,r) 

For i=1 To Anzahl 
Print(Str(SortmeF(i))+" ") 
Next i 

Input()