Alphabetisch sortieren

Übersicht

BlitzBasic

Allgemein

	Hubsi Betreff: Alphabetisch sortieren	Mi, März 03, 2004 2:13 Antworten mit Zitat
Hallo beisammen. Ich möchte eine Liste mit Wörtern die in einem Array gespeichert sind alphabetisch sortieren. Klingt ja eigentlich nicht sonderlich schwer, aber ich hab wohl gerade Gehirnkrämpfe
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

Betreff: Alphabetisch sortieren

Mi, März 03, 2004 2:13
Antworten mit Zitat

Hallo beisammen.

Ich möchte eine Liste mit Wörtern die in einem Array gespeichert sind alphabetisch sortieren. Klingt ja eigentlich nicht sonderlich schwer, aber ich hab wohl gerade Gehirnkrämpfe Smile

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	BladeRunner Moderator	Mi, März 03, 2004 2:20 Antworten mit Zitat
Nur so als Vorschlag: Wandle von jedem Wort den ersen Buchstaben in den Passenden Ascii-Wert um und sortiere dann mit Bubblesort. Dann eine Liste anlegen ab welchem Eintrag deiner Liste welcher Buchstabe beginnt und gruppenweise (also alle Wörter mit a... b... c...) das selbe Spiel mit dem Asciicode. So kannst du dich bis zum Ende durchhangeln (rekursiv?). Habs nit weiter durchgedacht, da ich noch Geburtstagfeiergeschädigt bin und allohol das logische denken nit unbedingt fördert...
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mi, März 03, 2004 2:20
Antworten mit Zitat

Nur so als Vorschlag:
Wandle von jedem Wort den ersen Buchstaben in den Passenden Ascii-Wert um und sortiere dann mit Bubblesort. Dann eine Liste anlegen ab welchem Eintrag deiner Liste welcher Buchstabe beginnt und gruppenweise (also alle Wörter mit a... b... c...) das selbe Spiel mit dem Asciicode.
So kannst du dich bis zum Ende durchhangeln (rekursiv?).
Habs nit weiter durchgedacht, da ich noch Geburtstagfeiergeschädigt bin und allohol das logische denken nit unbedingt fördert...

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Hubsi	Mi, März 03, 2004 10:19 Antworten mit Zitat
Das könnte klappen! Super Idee, danke
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

Mi, März 03, 2004 10:19
Antworten mit Zitat

Das könnte klappen! Super Idee, danke Mr. Green

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	Rallimen Sieger des 30-EUR-Wettbewerbs	Mi, März 03, 2004 10:43 Antworten mit Zitat
Hallo, es gibt da mehrere Varianten ein Arry zu sortieren mit Bubblesort <<<<sehr lahm wenn viele datenfelder Code: [AUSKLAPPEN] [EINKLAPPEN] Function bublesort() ; global maxfeld For I = 0 To maxfeld For J = I To maxfeld If feld$(I) > feld$(J) Then ; "<" = größter zuerst / ">" = kleinster zuerst X$ = feld$(I) : feld$(I) = feld$(J) : feld$(J) = X$ EndIf Next Next End Function hier meine eigene version ist schon doppelt so schnell wie Bubblesort:Code: [AUSKLAPPEN] [EINKLAPPEN] Function Rallisort(); global maxfeld While Not t = maxfeld;######## t = t +1 dummy1$ = feld$(t) For z = t To 1 Step -1 If feld$(z-1)> dummy1$ ;tauschen feld$(z) = feld$(z-1) Else Exit End If Next feld$(z) = dummy1$ Wend End Function jezt mal was richtig schnelles...... Quicksort ( ca 20 x schnellerals Bubblesort)Code: [AUSKLAPPEN] [EINKLAPPEN] Function quicksort(l,r) ; l = startwert : r = endwert Local p,q,h$ p=l q=r x$=Feld$ ((l+r)/2) Repeat While Feld (p)<x p=p+1 Wend While x<Feld (q) q=q-1 Wend If p>q Then Exit ;SWAP------------------ h$=Feld$ (q) :Feld $(q)=Feld$ (p) :Feld$(p)=h$ ;---------------------- p=p+1 q=q-1 If q<0 Then Exit Forever If l<q Then a=quicksort(l,q) If p<r Then a=quicksort(p,r) End Function quicksort ist fast immer das schnellste sortierprogramm! die 3 functionen sind jetzt für Strings gedacht! Noch schneller geht es wenn zb. ein datensatz einsortiert werden soll und der rest schon sortiert ist! wie bei einer highscore zB.
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Mi, März 03, 2004 10:43
Antworten mit Zitat

Hallo, es gibt da mehrere Varianten ein Arry zu sortieren
mit Bubblesort <<<<sehr lahm wenn viele datenfelder
Code: [AUSKLAPPEN]

Function bublesort() ; global maxfeld
For I = 0 To maxfeld
   For J = I To maxfeld
      If feld$(I) > feld$(J) Then ; "<" = größter zuerst / ">" = kleinster zuerst
         X$ = feld$(I) : feld$(I) = feld$(J) : feld$(J) = X$
      EndIf
   Next
Next
End Function

hier meine eigene version ist schon doppelt so schnell wie Bubblesort:Code: [AUSKLAPPEN]

Function Rallisort(); global maxfeld
While Not t = maxfeld;########
t = t +1
dummy1$ = feld$(t)
For z = t To 1 Step -1
   If feld$(z-1)> dummy1$ ;tauschen
      feld$(z) = feld$(z-1)
   Else
      Exit
   End If
Next
feld$(z) = dummy1$
Wend
End Function

jezt mal was richtig schnelles...... Quicksort ( ca 20 x schnellerals Bubblesort)Code: [AUSKLAPPEN]

Function quicksort(l,r) ; l = startwert : r = endwert
Local p,q,h$
p=l
q=r
x$=Feld$ ((l+r)/2)
Repeat
While Feld (p)<x
p=p+1
Wend
While x<Feld (q)
q=q-1
Wend
If p>q Then Exit
;SWAP------------------
h$=Feld$ (q) :Feld $(q)=Feld$ (p) :Feld$(p)=h$
;----------------------
p=p+1
q=q-1
If q<0 Then Exit
Forever
If l<q Then a=quicksort(l,q)
If p<r Then a=quicksort(p,r)
End Function

quicksort ist fast immer das schnellste sortierprogramm!
die 3 functionen sind jetzt für Strings gedacht!
Noch schneller geht es wenn zb. ein datensatz einsortiert werden soll und der rest schon sortiert ist!
wie bei einer highscore zB.

[BB2D | BB3D | BB+]

	Hubsi	Mi, März 03, 2004 11:42 Antworten mit Zitat
Danke, habs schon gebacken bekommen Hab einfach eine alte Highscore-Sortierfunction nach BladeRunner`s Idee umgebastelt. Nicht das schnellste, ist aber kein Problem, es muß ja nur einmal sortiert werden Code: [AUSKLAPPEN] [EINKLAPPEN] Function LevelSort(mm) Local a,temp$ For b=1 To mm For a=mm To 2 Step -1 If Asc(Left$(level$(a),1))<Asc(Left$(level$(a-1),1)) temp$=level$(a-1) level$(a-1)=level$(a) level$(a)=temp$ EndIf Next Next End Function
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

Mi, März 03, 2004 11:42
Antworten mit Zitat

Danke, habs schon gebacken bekommen Very Happy

Hab einfach eine alte Highscore-Sortierfunction nach BladeRunner`s Idee umgebastelt. Nicht das schnellste, ist aber kein Problem, es muß ja nur einmal sortiert werden Smile

Code: [AUSKLAPPEN]

Function LevelSort(mm)
Local a,temp$
For b=1 To mm
For a=mm To 2 Step -1
If Asc(Left$(level$(a),1))<Asc(Left$(level$(a-1),1))
temp$=level$(a-1)
level$(a-1)=level$(a)
level$(a)=temp$
EndIf
Next
Next
End Function

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	D2006 Administrator	Mi, März 03, 2004 12:30 Antworten mit Zitat
@Bladerunners Vorschlag: ist relatvi sinnlos, weil du ohne weiteres zwei string vergleichen kannst, wie es Rallimen anwendete. Code: [AUSKLAPPEN] [EINKLAPPEN] If "aaa" < "bbb" Then Text 10,10,"Toll!" ^^ funzt natürlich werden umlaute nicht berücksichtigt. MfG

D2006

Administrator

Mi, März 03, 2004 12:30
Antworten mit Zitat

@Bladerunners Vorschlag:
ist relatvi sinnlos, weil du ohne weiteres zwei string vergleichen kannst, wie es Rallimen anwendete.

Code: [AUSKLAPPEN]

If "aaa" < "bbb" Then Text 10,10,"Toll!"

^^ funzt

natürlich werden umlaute nicht berücksichtigt.

MfG

	Jan_ Ehemaliger Admin	Mi, März 03, 2004 13:13 Antworten mit Zitat
Und groß und klein schreibung, werden berücksichtigt! bei einen direckt vergleich, Aber, es könnte ein prob geben, bei unterschiedliche längen!
between angels and insects

Jan_

Ehemaliger Admin

Mi, März 03, 2004 13:13
Antworten mit Zitat

Und groß und klein schreibung, werden berücksichtigt!

bei einen direckt vergleich,
Aber, es könnte ein prob geben, bei unterschiedliche längen!

between angels and insects

	BladeRunner Moderator	Mi, März 03, 2004 13:41 Antworten mit Zitat
Nüchtern betrachtet muß ich meinen Vorrednern selbstredend recht geben... au Kopfweh
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mi, März 03, 2004 13:41
Antworten mit Zitat

Nüchtern betrachtet muß ich meinen Vorrednern selbstredend recht geben...

*au Kopfweh*

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Weazle25	Sa, Okt 16, 2004 19:46 Antworten mit Zitat
Ich plage mich schon seid ein paar Stunden damit rum ein Stringarray alphabetisch zu sortieren. Ich habe auch die obigen Beispiele ausprobiert und sie sind ALLE unbrauchbar. Grund: String1$ < String2$ funktioniert nicht da offenbar die ASCII-Werte aller Zeichen eines Strings addiert und dann beide Summen verglichen werden (wie sollte es auch sonst funktionieren). Nun habe ich selbst ne Funktion geschrieben: Code: [AUSKLAPPEN] [EINKLAPPEN] Function InitFiles() Dim TempFiles$(TempFilesMax) verz = ReadDir(MeshPath$) Repeat FileName$ = NextFile(verz) If FileName$ = "" Then Exit If Right(FileName$,4) = ".3ds" Then done = 0 TempFilesCount = TempFilesCount + 1 x=1 m=1 For x= 1 To TempFilesCount If Len(TempFiles$(x)) > Len(FileName$) Then Exit If Lower(Mid(TempFiles$(x),m,1)) < Lower(Mid(FileName$,m,1)) Then Exit If Lower(Mid(TempFiles$(x),m,1)) = Lower(Mid(FileName$,m,1)) Then If Len(TempFiles$(x)) > Len(FileName$) Then Exit For m=1 To Len(FileName$) If Lower(Mid(TempFiles$(x),m,1)) < Lower(Mid(FileName$,m,1)) Then x=x+1 done = 1 Exit EndIf Next EndIf If done = 1 Then Exit Next For y = TempFilesCount To x+1 Step -1 TempFiles$(y)=TempFiles$(y-1) Next TempFiles$(x) = FileName$ EndIf Forever CloseDir(verz) End Function Eigentlich funktioniert das schon (zumindest besser als bei den obigen Beispielen) aber ich habe immer noch 3 Probleme: 1. Es treten immer noch vereinzelt Sortierfehler auf. Wo ist also der Fehler? 2. Die Strings werden absteigend sortiert (Z->A). Wie kann ich die ändern? 3. Die Funktion ist zu langsam. Wie kann ich sie beschleunigen? Gruss Weazle

Weazle25

Sa, Okt 16, 2004 19:46
Antworten mit Zitat

Ich plage mich schon seid ein paar Stunden damit rum ein Stringarray alphabetisch zu sortieren.
Ich habe auch die obigen Beispiele ausprobiert und sie sind ALLE unbrauchbar.
Grund: String1$ < String2$ funktioniert nicht da offenbar die ASCII-Werte aller Zeichen eines Strings addiert und dann beide Summen verglichen werden (wie sollte es auch sonst funktionieren).

Nun habe ich selbst ne Funktion geschrieben:
Code: [AUSKLAPPEN]

Function InitFiles()
Dim TempFiles$(TempFilesMax)
verz = ReadDir(MeshPath$)
Repeat
   FileName$ = NextFile(verz)
   If FileName$ = "" Then Exit
   If Right(FileName$,4) = ".3ds" Then
      done = 0
      TempFilesCount = TempFilesCount + 1
      x=1
      m=1
      For x= 1 To TempFilesCount
         If Len(TempFiles$(x)) > Len(FileName$) Then Exit
         If Lower(Mid(TempFiles$(x),m,1)) < Lower(Mid(FileName$,m,1)) Then Exit
         If Lower(Mid(TempFiles$(x),m,1)) = Lower(Mid(FileName$,m,1)) Then
            If Len(TempFiles$(x)) > Len(FileName$) Then Exit
            For m=1 To Len(FileName$)
               If Lower(Mid(TempFiles$(x),m,1)) < Lower(Mid(FileName$,m,1)) Then
                  x=x+1
                  done = 1
                  Exit
               EndIf
            Next
         EndIf
         If done = 1 Then Exit
      Next

      For y = TempFilesCount To x+1 Step -1
         TempFiles$(y)=TempFiles$(y-1)
      Next
      TempFiles$(x) = FileName$
   EndIf
Forever
CloseDir(verz)
End Function

Eigentlich funktioniert das schon (zumindest besser als bei den obigen Beispielen) aber ich habe immer noch 3 Probleme:
1. Es treten immer noch vereinzelt Sortierfehler auf. Wo ist also der Fehler?
2. Die Strings werden absteigend sortiert (Z->A). Wie kann ich die ändern?
3. Die Funktion ist zu langsam. Wie kann ich sie beschleunigen?

Gruss
Weazle

	simi	Sa, Okt 16, 2004 20:31 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] ;Ausprobiert in einem Verzeichnis mit folgenden Dateien: ;a.bb ;aber.bbb ;aber.bbbb ;b.bb ;EditorV2.bb Dim TempFiles$(20) verz = ReadDir("C:\Test\") Repeat FileName$ = NextFile(verz) If FileName$ = "" Then Exit TempFilesCount = TempFilesCount + 1 For x= 1 To TempFilesCount For y = 1 To Len(FileName) If Lower(Mid(TempFiles$(x),y,1)) < Lower(Mid(FileName$,y,1)) Then Exit If Lower(Mid(TempFiles$(x),y,1)) > Lower(Mid(FileName$,y,1)) Then Goto weiter Next Next .weiter For y = TempFilesCount To x+1 Step -1 TempFiles$(y)=TempFiles$(y-1) Next TempFiles$(x) = FileName$ Forever For x = 0 To 10 Print TempFiles(x) Next WaitKey() CloseDir(verz) End 1. Du hast die Lange der beiden Strings verglichen, wenn du sie alphabetisch sortieren wolltest, das war denke ich mal der Fehler. Du musst jeden Buchstaben mit dem anderen vergleichen, dann geht es... 2. Dazu musst du in meinem code nur > und < als vertauschen.... 3. Da kann ich dir leider nicht helfen, denn ich checke die anderen Sortieralghorithmen nicht.... cu simi

simi

Sa, Okt 16, 2004 20:31
Antworten mit Zitat

Code: [AUSKLAPPEN]

;Ausprobiert in einem Verzeichnis mit folgenden Dateien:
;a.bb
;aber.bbb
;aber.bbbb
;b.bb
;EditorV2.bb

Dim TempFiles$(20)
verz = ReadDir("C:\Test\")
Repeat
FileName$ = NextFile(verz)
If FileName$ = "" Then Exit
TempFilesCount = TempFilesCount + 1
For x= 1 To TempFilesCount
   For y = 1 To Len(FileName)
      If Lower(Mid(TempFiles$(x),y,1)) < Lower(Mid(FileName$,y,1)) Then Exit
      If Lower(Mid(TempFiles$(x),y,1)) > Lower(Mid(FileName$,y,1)) Then Goto weiter
   Next
Next
.weiter
For y = TempFilesCount To x+1 Step -1
   TempFiles$(y)=TempFiles$(y-1)
Next
TempFiles$(x) = FileName$
Forever
For x = 0 To 10
Print TempFiles(x)
Next
WaitKey()
CloseDir(verz)
End

1. Du hast die Lange der beiden Strings verglichen, wenn du sie alphabetisch sortieren wolltest, das war denke ich mal der Fehler. Du musst jeden Buchstaben mit dem anderen vergleichen, dann geht es...
2. Dazu musst du in meinem code nur > und < als vertauschen....
3. Da kann ich dir leider nicht helfen, denn ich checke die anderen Sortieralghorithmen nicht.... Very Happy

cu simi

	Gerhard	Sa, Okt 16, 2004 20:40 Antworten mit Zitat
Ich bin mit der Variante von D2006 bisher immer bestens bedient gewesen. Allerdings wandle ich für den Vergleich immer in Großbuchstaben um: if upper$("aaa") < upper$("bbb") then Text 10,10,"kleiner"

Gerhard

Sa, Okt 16, 2004 20:40
Antworten mit Zitat

Ich bin mit der Variante von D2006 bisher immer bestens bedient gewesen. Allerdings wandle ich für den Vergleich immer in Großbuchstaben um:

if upper$("aaa") < upper$("bbb") then Text 10,10,"kleiner"

	Weazle25	Sa, Okt 16, 2004 22:23 Antworten mit Zitat
simi hat Folgendes geschrieben: 1. Du hast die Lange der beiden Strings verglichen, wenn du sie alphabetisch sortieren wolltest, das war denke ich mal der Fehler. Du musst jeden Buchstaben mit dem anderen vergleichen, dann geht es... Es funktioniert tatsächlich. Jetzt muss ich nur noch sehen das ich die leeren Strings raus bekomme. simi hat Folgendes geschrieben: 2. Dazu musst du in meinem code nur > und < als vertauschen.... Das hatte ich gemacht aber die Reihenfolge der sortierten Strings hatte sich nicht geändert. Da war wohl irgendwo noch ein Fehler drin. simi hat Folgendes geschrieben: 3. Da kann ich dir leider nicht helfen, denn ich checke die anderen Sortieralghorithmen nicht.... cu simi Ich auch nicht. Gruss Weazle

Weazle25

Sa, Okt 16, 2004 22:23
Antworten mit Zitat

simi hat Folgendes geschrieben:

Es funktioniert tatsächlich.
Jetzt muss ich nur noch sehen das ich die leeren Strings raus bekomme.

simi hat Folgendes geschrieben:

2. Dazu musst du in meinem code nur > und < als vertauschen....

Das hatte ich gemacht aber die Reihenfolge der sortierten Strings hatte sich nicht geändert.
Da war wohl irgendwo noch ein Fehler drin.

simi hat Folgendes geschrieben:

3. Da kann ich dir leider nicht helfen, denn ich checke die anderen Sortieralghorithmen nicht.... Very Happy

cu simi

Ich auch nicht. Embarassed

Gruss
Weazle

	Weazle25	Sa, Okt 16, 2004 22:24 Antworten mit Zitat
Gerhard hat Folgendes geschrieben: Ich bin mit der Variante von D2006 bisher immer bestens bedient gewesen. Allerdings wandle ich für den Vergleich immer in Großbuchstaben um: if upper$("aaa") < upper$("bbb") then Text 10,10,"kleiner" Dann dürften aber die Strings "abc" und "cba" gleich gross sein. Gruss Weazle

Weazle25

Sa, Okt 16, 2004 22:24
Antworten mit Zitat

Gerhard hat Folgendes geschrieben:

Dann dürften aber die Strings "abc" und "cba" gleich gross sein.

Gruss
Weazle

	D2006 Administrator	Sa, Okt 16, 2004 23:25 Antworten mit Zitat
Schwachsinn! Probier es doch einfach aus! Genau wie ich vor Jahrzehnten. Also hier eine Erklärung was ich unter Bubblesort verstehe: Man hat ein Array mit Strings gefüllt. Man will sie aufsteigend (von A bis Z) sortieren. Hier für nimmt man logischer Weise eine For ... Next Schleife und geht jeden Wert von vorn bis hinten durch. Dabei wird der entsprechende Wert mit dem nachfolgendem verglichen. Ist der Wert größer als sein Nachfolger, so vertauscht man beide Werte. Wenn man diese Schleife einmal durchlaufen lässt, ist der größte Wert (z.B. "Zwickau" ) hinten. Bei 2. Durchlauf ist der zweit größte an vorletzter Stelle, ... logisch. Also brauch man höchstens (Anzahl der Felder)-1 Durchläufe. Das kann man nun also eine weitere For Next Schleife drum rum setzen oder wie ich es mache: Code: [AUSKLAPPEN] [EINKLAPPEN] Repeat swap=0 ... ;Schleife für Durchlauf ;wenn getauscht wird, setzt man für swap 1. ... Until swap=0 ;Bis nicht mehr getauscht wurde, weil dann ist er ja fertig ^^ diese Methode kann manchmal einen Durchlauf mehr als benötigt beanspruchen aber in den meisten Fällen spart man Zeit. Übrigens: der Quicksort Algorithmus wird ganz schön lahm, wenn das Array total durcheinander ist. MfG D2006

D2006

Administrator

Sa, Okt 16, 2004 23:25
Antworten mit Zitat

Schwachsinn!

Probier es doch einfach aus! Genau wie ich vor Jahrzehnten.

Also hier eine Erklärung was ich unter Bubblesort verstehe:
Man hat ein Array mit Strings gefüllt. Man will sie aufsteigend (von A bis Z) sortieren.
Hier für nimmt man logischer Weise eine For ... Next Schleife und geht jeden Wert von vorn bis hinten durch. Dabei wird der entsprechende Wert mit dem nachfolgendem verglichen. Ist der Wert größer als sein Nachfolger, so vertauscht man beide Werte.

Wenn man diese Schleife einmal durchlaufen lässt, ist der größte Wert (z.B. "Zwickau" Wink

) hinten. Bei 2. Durchlauf ist der zweit größte an vorletzter Stelle, ... logisch. Also brauch man höchstens (Anzahl der Felder)-1 Durchläufe. Das kann man nun also eine weitere For Next Schleife drum rum setzen oder wie ich es mache:

Code: [AUSKLAPPEN]

Repeat
swap=0
...
;Schleife für Durchlauf
;wenn getauscht wird, setzt man für swap 1.
...
Until swap=0 ;Bis nicht mehr getauscht wurde, weil dann ist er ja fertig

^^ diese Methode kann manchmal einen Durchlauf mehr als benötigt beanspruchen aber in den meisten Fällen spart man Zeit.

Übrigens: der Quicksort Algorithmus wird ganz schön lahm, wenn das Array total durcheinander ist.

MfG
D2006

	hot-bit Gast	Sa, Okt 16, 2004 23:54 Antworten mit Zitat
Hoi.. Dann machst aber irgendwas falsch. Quicksort ist eine der schnellsten Routinen ! Toni

hot-bit

Gast

Sa, Okt 16, 2004 23:54
Antworten mit Zitat

Hoi..

Dann machst aber irgendwas falsch.

Quicksort ist eine der schnellsten Routinen !

Toni

	D2006 Administrator	So, Okt 17, 2004 0:07 Antworten mit Zitat
Zitat: Im (seltenen) schlechtesten Fall ist es mit einer Zeitkomplexität von (n2) allerdings genauso langsam wie Insertion Sort Quelle: http://www.iti.fh-flensburg.de.../quick.htm Zitat: QuickSort liegt im worst case in der Aufwandsklasse O(n²), im Mittel in der Aufwandsklasse O(n·log(n)). Quelle: http://de.wikipedia.org/wiki/Quicksort Zitat: Ungünstigster Fall: diesen beobachtet man dann, wenn eines der beiden Stücke nur ein Element enthält. In diesem ungünstigsten Fall ruft sich quicksort() N-mal selber auf (N=Anzahl der Feldelemente), zudem benötigt der Algorithmus N2/2 Vergleiche, hat also dieselbe Laufzeitkomplexität wie BubbleSort ... Quelle: http://www.linux-related.de/in..._quick.htm Anmerkung: sehr gute Seite! Wenn noch mehr Beweise erwünscht sind, bitte melden! MfG D2006

D2006

Administrator

So, Okt 17, 2004 0:07
Antworten mit Zitat

Zitat:

Im (seltenen) schlechtesten Fall ist es mit einer Zeitkomplexität von (n2) allerdings genauso langsam wie Insertion Sort

Quelle: http://www.iti.fh-flensburg.de.../quick.htm

Zitat:

QuickSort liegt im worst case in der Aufwandsklasse O(n²), im Mittel in der Aufwandsklasse O(n·log(n)).

Quelle: http://de.wikipedia.org/wiki/Quicksort

Zitat:

Ungünstigster Fall: diesen beobachtet man dann, wenn eines der beiden Stücke nur ein Element enthält. In diesem ungünstigsten Fall ruft sich quicksort() N-mal selber auf (N=Anzahl der Feldelemente), zudem benötigt der Algorithmus N2/2 Vergleiche, hat also dieselbe Laufzeitkomplexität wie BubbleSort ...

Quelle: http://www.linux-related.de/in..._quick.htm
Anmerkung: sehr gute Seite!

Wenn noch mehr Beweise erwünscht sind, bitte melden!

MfG
D2006

	Rallimen Sieger des 30-EUR-Wettbewerbs	So, Okt 17, 2004 0:42 Antworten mit Zitat
Bubblesort ist einfach zu proggen, dafür aber bei großen Mengen viel zu langsam! Toni hat da vollkommen recht mit der Ausssage das Quicksort normalerweise das schnellste ist, auch wenn das Array voll gut gemischt ist! Das ist auch meine Meinung! Aber warum auf Stringlängen sortiert werden soll ......ist mir noch ein Rätsel!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

So, Okt 17, 2004 0:42
Antworten mit Zitat

Bubblesort ist einfach zu proggen, dafür aber bei großen Mengen viel zu langsam!
Toni hat da vollkommen recht mit der Ausssage das Quicksort normalerweise das schnellste ist, auch wenn das Array voll gut gemischt ist!
Das ist auch meine Meinung!
Aber warum auf Stringlängen sortiert werden soll ......ist mir noch ein Rätsel!

[BB2D | BB3D | BB+]

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Alphabetisch sortieren

Betreff: Alphabetisch sortieren

hot-bit