Entwickler-Ecke :: Thema anzeigen - Buchstaben eines Wortes alphabetisch sortieren ?

matze - Di 05.04.05 19:15
Titel: Buchstaben eines Wortes alphabetisch sortieren ?

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

Gausi - Di 05.04.05 20:40

Schnelle Algorithmen findest du z.B. hier:

http://www.delphi-forum.de/topic_quick+Sort_35313.html
http://www.delphi-forum.de/topic_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.

zemy - 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 :D

MfG Zemy

Popov - 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;

tommie-lie - 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 :mrgreen:

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 :mrgreen:

tommie-lie - Di 05.04.05 22:36

Popov hat folgendes geschrieben:

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 ;)

Nein, ich hatte es auch aus dem Kopf getippt, den Bubblesort habe ich mir immer nur mit der Prüfung, ob getauscht wurde, gemerkt ;-)

opfer.der.genauigkeit - Di 05.04.05 22:52

Ich kann's mir nicht verkneifen :mrgreen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

var
  s   : string;
  i   : integer;
  List: TStringList;
begin
  s := 'matze';

  List := TStringList.Create;
  List.Sorted := true;

  for i := 1 to Length(s) do begin
    List.Add(s[i]);
  end;
end;

:rofl:

uall@ogc - 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

matze - Do 07.04.05 13:51

aaargh. da schaut man mal nen tag lang nicht ins forum und schon wird man erschlagen vor hilfe :wink:

ich danke euch allen tausendmal.
ihr habt mir sehr geholfen !

@opfer.der.genauigkeit:
Das ist auch das was mir als allererstes eingefallen ist :wink: :wink:

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!