Autor |
Beitrag |
matze
Beiträge: 4613
Erhaltene Danke: 24
XP home, prof
Delphi 2009 Prof,
|
Verfasst: Di 05.04.05 19:15
Hallo !
Ich habe folgendes Problem:
Ich muss (mit einem möglichst schnellen Algo) die Buschtaben eines Wortes dem Alphabet nach sortieren.
also aus matze sollte aemtz werden.
wie kann ich das am besten machen ?
danke Moderiert von Christian S.: Topic aus Sonstiges verschoben am Di 05.04.2005 um 19:53
_________________ In the beginning was the word.
And the word was content-type: text/plain.
|
|
ScorpionKing
Beiträge: 1150
Win XP
|
Verfasst: Di 05.04.05 19:58
Also ich würde mal sagen: BubbleSort oder ShellSort!
DELPHI QUICKSORT
MfG, ScorpionKing!
_________________ Aus dem Urlaub zurück!
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Di 05.04.05 20:40
Schnelle Algorithmen findest du z.B. hier:
www.delphi-forum.de/...uick+Sort_35313.html
www.delphi-forum.de/...mergesort_35402.html
Für kurze Wörter reicht aber auch ein Bubblesort. Und da ein String ja ansprechbat wie ein Array ist, sollte das ganze kein Problem sein.
_________________ We are, we were and will not be.
|
|
zemy
Beiträge: 207
Win XP Prof.
D7
|
Verfasst: Di 05.04.05 20:45
mit Zahl:=ord(thestring[123]) kannst du den Zahlenwert (Ascii-Code) des gewählten Zeichens abgreifen. theString[123]:=chr(213); weist einem Zeichen dann einen (ASCII) Wert zu. Das währe schon mal das tauschen und vergleiche könnte man auch darüber machen...
Wenn du allerdings auf Spagethicode stehst, kannst du einen Pointer definieren, der auf ein entsprechend langes Array aus Bytes zeigt (so lang wie es Buchstaben gibt) und diesen auf das erste Element des Strings zeigen lassen. Dieses kannst du dann (fast) wie ein normales Array behandeln und sortieren.... gibt natürlich Probleme bei Zeichen, die mehr als ein Byte belegen, ist aber sowieso keine saubere Lösung
MfG Zemy
_________________ LifeIsToShortToThinkAboutTheShortness
|
|
Popov
Beiträge: 1655
Erhaltene Danke: 13
WinXP Prof.
Bei Kleinigkeiten D3Pro, bei größeren Sachen D6Pro oder D7
|
Verfasst: Di 05.04.05 20:53
Du mußt da zwar noch paar Sicherheitspunkte einbauen, aber das Sortieren geht in etwa so:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| procedure TForm1.Button1Click(Sender: TObject); var s: String; c: Char; i, k: Integer; begin s := 'matze';
for k := 1 to Length(s) do for i := 2 to Length(s) do begin if s[i] < s[i-1] then begin c := s[i]; s[i] := s[i-1]; s[i-1] := c; end; end;
ShowMessage(s); end; |
_________________ Popov
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Di 05.04.05 22:15
Popov hat folgendes geschrieben: | das Sortieren geht in etwa so: |
Hmm... Er fragte extra nach einem schnellen Algorithmus, ob Bubblesort da die richtige Wahl ist? Bei 'matze' sicherlich kein Problem, aber wer weiß was ihm da für Wörter einfallen
However, auch die Version des Bubblesorts lässt sich noch ein wenig optimieren, da sie unnötig oft Schleifen durchläuft, was nicht nötig wäre:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
| procedure TForm1.Button1Click(Sender: TObject); var s: String; c: Char; i, k: Integer; items_exchanged: Boolean; begin s := 'matze';
repeat items_exchanged := False; for i := 2 to Length(s) do begin if s[i] < s[i-1] then begin c := s[i]; s[i] := s[i-1]; s[i-1] := c; items_exchanged := True; end; end; until not items_exchanged;
ShowMessage(s); end; | Bei fünf Buchstaben außerhalb des Messbaren, aber immerhin
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
delfiphan
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Di 05.04.05 22:27
=> Bucketsort (Aka Radix Sort) mit linearer Sortierungszeit, da es nur 256 Elemente gibt.
|
|
Popov
Beiträge: 1655
Erhaltene Danke: 13
WinXP Prof.
Bei Kleinigkeiten D3Pro, bei größeren Sachen D6Pro oder D7
|
Verfasst: Di 05.04.05 22:29
War in einer Minute aus dem Kopf getippt und sollte nur das Prinzip zeigen. Schön daß du in einer FAQ nachgesehen hast und es verbessert hast
_________________ Popov
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Di 05.04.05 22:36
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
opfer.der.genauigkeit
Beiträge: 754
Erhaltene Danke: 1
|
Verfasst: Di 05.04.05 22:52
_________________ Stellen Sie sich bitte Zirkusmusik vor.
|
|
uall@ogc
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 05.04.05 22:54
jedenfalls kann man buchstaben genau so sortieren wie zahlen
Quicksort, Mergesort Heapsort mit laufzeit n * log (n)
oder nucksetsort (denke mal das der das ist)
wo du nen array machst und alle buchstaben zählst, und dann einfach wieder ausgibst je nachdem wie oft welcher vorkam
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
matze
Beiträge: 4613
Erhaltene Danke: 24
XP home, prof
Delphi 2009 Prof,
|
Verfasst: Do 07.04.05 13:51
aaargh. da schaut man mal nen tag lang nicht ins forum und schon wird man erschlagen vor hilfe
ich danke euch allen tausendmal.
ihr habt mir sehr geholfen !
@opfer.der.genauigkeit:
Das ist auch das was mir als allererstes eingefallen ist
_________________ In the beginning was the word.
And the word was content-type: text/plain.
|
|