PureBoard

Verfasst: **16.11.2004 15:00**

heyho!

ich hab da eine frage: gibt es eine function mit der man einen string sortieren kann? z.b. "fkjghdfsk234962" halt ziffern nach aufsteigender groesse und dann buchstaben nach alphabet?

falls nicht, kann einer mal so eine procedure basteln?

dankö

Verfasst: **16.11.2004 15:25**

du kannst zeichen für zeichen in ein array einlesen und dieses dann mit SortArray() nach wunsch sortieren.

Verfasst: **16.11.2004 15:27**

@MLK: das ist doch quatsch, da programmiert man sich das schnell selbst:

Code: Alles auswählen

Procedure ChangeLetters(*String, Index1, Index2)
  l1.b = PeekB(*String+Index1)
  PokeB(*String+Index1, PeekB(*String+Index2))
  PokeB(*String+Index2, l1)
EndProcedure

Procedure.s SortString(String.s, Flag) ;Flags: 0=abc 1=cba
  If Flag = 0
    For k=1 To Len(String.s)
      cur = Asc(Mid(String, k, 1))
      For i=k To Len(String)
        If Asc(Mid(String, i, 1)) < cur
          ChangeLetters(@String, k-1, i-1)
          String = SortString(String.s, Flag)
          Break 2
        EndIf
      Next
    Next
  Else
    For k=1 To Len(String.s)
      cur = Asc(Mid(String, k, 1))
      For i=k To Len(String)
        If Asc(Mid(String, i, 1)) > cur
          ChangeLetters(@String, k-1, i-1)
          String = SortString(String.s, Flag)
          Break 2
        EndIf
      Next
    Next
  EndIf
  ProcedureReturn String
EndProcedure

Text.s = "a3cc2ba1"
Debug Text
Debug SortString(Text, 0)
Debug SortString(Text, 1)

Verfasst: **16.11.2004 15:34**

@DarkDragon

...ist das der berühmte QuickSort-Algo ? ...ich weiss den nichmehr genau...

Verfasst: **16.11.2004 16:05**

Ja isser. Der ist nämlich der einfachste.

Verfasst: **16.11.2004 16:09**

@DarkDragon: ist kein Quatsch:

Code: Alles auswählen

Procedure ChangeLetters(*String, Index1, Index2) 
  l1.b = PeekB(*String+Index1) 
  PokeB(*String+Index1, PeekB(*String+Index2)) 
  PokeB(*String+Index2, l1) 
EndProcedure 

Procedure.s SortString(String.s) ;Flags: 0=abc 1=cba 
  For k=1 To Len(String.s) 
    cur = Asc(Mid(String, k, 1)) 
    For i=k To Len(String) 
      If Asc(Mid(String, i, 1)) > cur 
        ChangeLetters(@String, k-1, i-1) 
        String = SortString(String.s) 
        Break 2 
      EndIf 
    Next 
  Next 
  ProcedureReturn String 
EndProcedure 

Procedure.s SortString2(String.s)
  Protected Length
  Length = Len(String)
  
  Dim string.b(Length)
  CopyMemory(@String, @string(), Length)
  SortArray(string(),3)
  CopyMemory(@string(), @String, Length)
  Dim string.b(0)
  
  ProcedureReturn String
EndProcedure


Text.s = "a3cc2ba1" 
Debug Text 
Debug SortString(Text)
Debug "-----------"
Debug SortString2(Text)

time1 = ElapsedMilliseconds()
For z = 0 To 1000000
  SortString(Text)
Next
time1 = ElapsedMilliseconds() - time1

time2 = ElapsedMilliseconds()
For z = 0 To 1000000
  SortString2(Text)
Next
time2 = ElapsedMilliseconds() - time2

MessageRequester("", Str(time1) + "  " + Str(time2))

Kann jetzt auch n Denkfehler drinhaben, hoffe aber nicht

Verfasst: **16.11.2004 16:14**

@remi

...nun, wahrscheinlich ist im Sort_Array der quicksort in ASS implementiert..

...könnte ja DarkDragon auch noch machen, dann wird der bestimmt in 'ne LIB dazugestellt...

Verfasst: **16.11.2004 16:22**

Seine Prozedur ist wahrscheinlich vor allem langsamer, weil:
- Nicht Asm (weiss zwar nicht ob PB-Lib hier in ASM geschr wurde)
- Rekursiv
- Funktionsaufruf ChangeLetters
- Mid() anstatt Pointer
Weiss eben eigentlich nicht, ob PBs Algo nicht auch rekursiv und nicht in Asm geschrieben wurde, vermute ich aber wegen dem grossen Zeitunterschied

PS: Ich weiss er kanns besser

Verfasst: **16.11.2004 16:27**

quicksort IST definitiv das nonplusultra in punkto geschwindigkeit/kürze..

...kann mir ehrlich gesagt kaum vorstellen, dass SortArray nen anderen algo benutzt... nur in ASM und mit pointers ist der latürnich x-mal schneller

Verfasst: **16.11.2004 16:34**

Würde hier nicht auf definitiv beharren! Kommt immer auf die Daten an, die du dem Algorithmus übergibst. Er ist aber sicher ein sehr schneller Kompromiss zwischen den einzelnen Sortieralgos

Bubble Sort, Insertion Sort, Quicksort, Selection Sort, Shellsort,...
jeder hat seine Vorteile! Ich glabe, dass Quicksort vor allem bei schon relativ sortierten einträgen nicht gerade schnell ist, kann mich aber auch irren.
Ausserdem sind rekursive Algos meist langsamer als ihre nichtrekursiven Verwandten

wenn du mit "geschwindigkeit/kürze" das Verhältnis zwischen Geschwindigkeit und Codekürze meinst, könntest du vielleicht sogar recht haben

greetz
remi