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