Seite 1 von 1
QUICKSORT ...es funktioniert nicht... wer hilft mir ?
Verfasst: 03.12.2004 21:50
von Gerhard
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.
Verfasst: 04.12.2004 09:19
von ChaOsKid
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
Verfasst: 04.12.2004 10:28
von Gerhard
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
Verfasst: 04.12.2004 13:53
von NicTheQuick
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.
Verfasst: 04.12.2004 16:48
von Falko
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
Verfasst: 04.12.2004 17:15
von remi_meier
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
Verfasst: 04.12.2004 18:04
von Froggerprogger
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
Verfasst: 04.12.2004 20:18
von Falko
remi_meier hat geschrieben:Vielleicht will jemand diesen Code von mir anpassen?
@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
Verfasst: 04.12.2004 23:08
von Andre
@Nic: mit dem alten Code im CodeArchiv austauschen, werde ich beim Update mit berücksichtigen.
Verfasst: 04.12.2004 23:56
von Falko
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()