Alphanumerische Stringsortierung

[Codehunter]

Guten Morgen!

Kurze Frage: Wie kann ich am einfachsten eine Liste (OnCompare beim VST, aber prinzipiell egal) in folgender Weise sortieren:

Abcde
BCDeF
cDefG
DEFGH
efghi
01345
12345
23456
34abc

Also case-insensitiv, Nummern nach Buchstaben.

Grüße
Cody

[hoika]

Hallo,
case-insensitiv: UpperCase verwenden.
Zahlen nach Buchstaben -> eigene Zeichen-Compare-Methode, also jedes Zeichen einzelnen vergleichen (TryStrtoInt benutzen, um zwischen Zahlen und Zeichen zu unterscheiden)

[peterbelow]

Delphi-Quellcode:

program RioTestframe_console;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, system.classes, system.character, system.math;
const
  testdata: array [0..11] of string =
  (
'cDefG',
'Abcde',
'Abc12',
'34abc',
'12345',
'BCDeF',
'BCDeFmm',
'efghi',
'efghi',
'01345',
'DEFGH',
'23456'
);

function SortCompare(List: TStringlist; i1, i2: integer): integer;
var
  S1, S2: string;
  I: Integer;
begin
  S1 := list[i1].ToUpper;
  S2 := list[i2].ToUpper;
  if Length(S2) = 0 then
    result := 1
  else if Length(S1) = 0 then
    result := -1
  else begin
    for I := 1 to Min(Length(S1), Length(S2)) do begin
      if S1[I].IsDigit = S2[I].IsDigit then
        result := ord(S1[I]) - ord(S2[I])
      else if S1[I].IsDigit then
        result := 1 // digits sort above letters
      else
        result := -1;
      if result <> 0 then
        exit;
    end; // for
  end; // else
  if result = 0 then
    // if both are equal for the length of the smaller string the longer wins
    result := length(S1) - length(S2);
end;

procedure RunTest;
var
  L: TStringlist;
  I: Integer;
begin
  L:= TStringlist.Create;
  try
    for I := Low(testdata) to High(testdata) do
      L.Add(testdata[I]);
    L.CustomSort(SortCompare);
    writeln(L.Text);
  finally
    L.Free;
  end;
end;


begin
  try
   RunTest;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  WriteLn(SLinebreak, 'Hit return to exit');
  ReadLn;
end.

[Delphi.Narium]

Kennt VST (analog zu TStringList) eine Methode CustomSort?

Eventuell geht auch das Ereignis

Delphi-Quellcode:

TVTCompareEvent = procedure(Sender: TBaseVirtualTree; Node1, Node2: PVirtualNode; Column: TColumnIndex; var Result: Integer) of object;

In der Ereignisroutine kannst Du dann Vergleiche nach "Deinem Gutdünken" beeinflussen.
Nur als hingedaddelte Idee (ohne irgendeine Garantie für irgendwas ;-))

Delphi-Quellcode:

procedure TForm1.OnTVTCompare(Sender: TBaseVirtualTree; Node1, Node2: PVirtualNode; Column: TColumnIndex; var Result: Integer);
Var
  Data1 : String;
  Data2 : String;
  IsNumber1 : Boolean;
  IsNumber2 : Boolean;
  l1 : Integer;
  l2 : Integer;
  i : Integer;
begin
  Data1 := Node1.Data; // Muss sicherlich irgendwie angepasst werden.
  Data2 := Node2.Data; // dito.
  // Rückgabewert = 0: Node1 und Node2 sind gleich
  // Rückgabewert < 0: Node1 ist kleiner als Node2
  // Rückgabewert > 0: Node2 ist größer als Node1
  Result := 0; // Wie gehen einfach erstmal von Gleichheit aus.
  // Zuerst auf Gleichheit prüfen.
  // Ist sie gegeben, können wir die Routine verlassen, der Rückgabewert ist mit 0 ok.
  if Data1 = Data2 then exit
  else begin
    l1 := Length(Data1);
    l2 := Length(Data2);
    for i := Min(l1,l2) do begin
      // Feststellen, ob beide nummerisch sind:
      // Normalerweise sind nummerische Werte < als Zeichen.
      IsNumber1 := Data1[i] < 'A';
      IsNumber2 := Data2[i] < 'A';
      // Zahl 1 ist größer als Buchstabe 2
      If IsNumber1 and not IsNumber2 then Result := 1 else
      // Zahl 2 ist größer als Buchstabe 1
      If IsNumber2 and not IsNumber1 then Result := -1 else
      // Zeichen ohne Beachtung von Groß-/Kleinschreiung vergleichen.
      // Der Rückgabewert von AnsiCompareText ist kompatibel zu dieser Routine.
      Result := AnsiCompareText(Data1[i],Data2[i]);
      // Ist Result nicht mehr = 0, so wurde ein Unterschied festgestellt
      // und wir können die Schleife verlassen.
      if Result <> 0 then break;
    end;  
    // Ist hier Result = 0 dann ergibt sich das Ergebnis aus dem Längenunterschied:
    if Result = 0 then Result := l1 - l2;
  end;
end;

Was ich nicht weiß ist, ob die Sortierung auch bei sowas noch annähernd richtig wird:

Code:

AbcdeA
Abcdeb
Abcdeba
Abcdeba1
Abcdeba2
Abcde1
Abcde2
BCDeF0A
BCDeF0B
BCDeF01
01345aB
01345AC
01345a1

Und mir ist klar, dass .Data im realen Leben nicht wirklich miteinander verglichen werden können, Du musst hier also eine für Deine Daten passende "Alternative" einbauen ;-)

[Codehunter]

Danke euch! Aus den Vorschlägen habe ich eine eigene Sortierfunktion erstellt, die macht was sie soll. Generell habe ich mir nur angewöhnt, erstmal nachzuschauen ob es nicht evtl. in der RTL oder im Win32 API irgendwas fertiges gibt.

[Delphi.Narium]

Könntest Du bitte Deine Lösung bitte posten. Mich würde schon sehr interessieren, wie es denn nun in der Realität wirklich funktioniert.

[Codehunter]

Ich glaube nicht dass dadurch so viel Erhellung geschehen würde wie du annimmst. Die konkrete Problemstellung ist sehr fallspezifisch. Daher müsste ich viel zurückbauen damit sich das allgemein anwenden ließe. Im wesentlichen vergleiche ich byteweise und werte alles zwischen 48 und 57 grundsätzlich kleiner als alles zwischen 65..90 und 97..122.

Überrascht hat mich nur die Performance. Ich hätte erwartet, dass es eher gemächlich wäre. Aber gut 40.000 Strings zwischen 5 und 30 Zeichen länge sind in < 100 ms sortiert.

[Delphi.Narium]

Der Vergleich der ASCII-Werte erscheint mit klever, dürfte die Logik deutlich übersichtlicher machen.