Buchstaben im String sortieren?

[ReCoVeR]

huhu wollte mal fragen, wie ich die Buchstaben von einem String sortieren kann

also aus "test"


soll "estt" werden..


thX schonmal

[Matze]

Mittels ASCII-Code geht das.
Man muss den dann so wie zahlen behandeln und das Sortieren ist dann ganz einfach.

[MikeS]

moin

du kannst mittels abfrage auch direkt buchstaben miteinander vergleichen!
if 'a' < 'b' then

[BungeeBug]

Hi,

ich hätte da ne "schnellere" Idee.

Delphi-Quellcode:

var
 MyStringList : TStringList;
 i : integer;
begin
 MyStringList := TStringList.Create;
 
 for i := 1 to Length(s) do
  begin
   MyStingList.Add(s[i]);
  end;
 
 s := ''; 
 MyStringList.Sort;
 
 for i := 0 to MyStringList.Item.Count -1 do
  begin
   s := s + MyStringList.Item[i];
  end;

 MyStringList.Free;
  
end;

Ist aber grad so aus dem Kopf entstanden. Könnte also sein das ein paar von den Funktionen nicht stimmen oder anders geschrieben werden.

[MikeS]

@BungeeBug
du solltest s spätestens nach dem sortienen leeren,
weil du an den vorhandenen einfach den sortierten wieder ranhängst!

ansonsten habe ich an deine möglichkeit auch schon gedacht!

[BungeeBug]

Zitat von MikeS:

@BungeeBug
du solltest s spätestens nach dem sortienen leeren,
weil du an den vorhandenen einfach den sortierten wieder ranhängst!

ansonsten habe ich an deine möglichkeit auch schon gedacht!

Hab ich doch

[MikeS]

da habe ich mich dann wohl geirrt!
oder doch nicht????

[choose]

Hallo ReCoVer,

theoretisch handelt es sich bei Deinem Problem zwar um das Sortieren einer geordneten (nicht sortieren!) eindimensionalen Struktur, so dass Du einen der klassischen Algorithmen anwenden könntest. Tatsächlich jedoch kannst Du die Kenntnis über die Beschaffenheit der Elemente (jedes im Intervall [#0..#255]) und die Tatsache, dass die Delphi-Strings weniger als 4 Milliarden (genau: 2^31 also etwa 2 Milliarden) fassen können, ausnutzen:
Ein denkbarer Ansatz wäre mit diesen Informationen, ein Array aufzuspannen, für das für jedes denkbare der 256 Zeichen einen Zähler hält. Iteriere über den Eingangsstring und zähle, wie oft die Zeichen vorkommen. Um nun die Ausgabe zu erstellen, iterierst Du über das Zählerarray und hängst das jeweilige Zeichen sooft an das bisherige Ergebnis, wie Du es beim Eingangsstring gezählt hast. Die Sortierung erhältst Du so "gratis", weil Dein Zählarray direkt über den ASCII-Wert des Zeichens, das gleichzeitig dem Kriterium der Ordnungsrelation entspricht, indiziert wird.

Anbei eine ad hoc-Implementierung (nur zur Anschauung, gerade das Konkatenieren könnte optimiert werden):

Delphi-Quellcode:

function SortString(const AString: string): string;
var
  arChars: array[Char] of Cardinal;
  myChar: Char;
  iChar: Integer;
begin
  // set every counter to zero
  FillChar(arChars, SizeOf(arChars), 0);

  // scan every char in string and increase counter for each
  //  found character by one
  for iChar:= 1 to Length(AString) do
    Inc(arChars[AString[iChar]]);

  Result:= '';
  // append found matches to result
  for myChar:= Low(myChar) to High(myChar) do
    Result:= Result+DupeString(myChar, arChars[myChar]);
end;

EDIT: Das beschriebene Verfahren nennt man iÜ Bucket Sort und ist neben der Einfachheit auch noch mit der Komplexität O(n) effizienter als die untere Schranke von auf Vergleichen basierenden Algorithmen O(n*log(n))

[sakura]

Anbei mal ein Demoprogramm mit drei total unterschiedlichen Ansätzen zur Sortierung (alle drei arbeiten nach dem ANSI Satz )

......

[negaH]

@Choose, danke das du diesen doch weniger bekannten Ansatz angesprochen hast. In fakt, für die gestellte Aufgabe ist Chooses Vorschlag bei weitem der effizienteste.

Gruß Hagen