Intelligentes BubleSort; sortieren wie im Windows Explorer

[Popov]

Sortiert man eine Liste wie: "Text 2", "Text 5", "Text 10", ergibt sich alphabetisch folgende Sortierung: "Text 2", "Text 10", "Text 5". Die 10 landet vor der 5, da die 1 der 10 alphabetisch vor der 5 steht. Folgende BubbleSortExtra Funktion sortiert die Liste zuerst alphabetisch, im zweiten Durchgang wird die erste Zahl der Strings nach Wert sortiert

Code:

Text
Text X
Text 1
Text 3
Text 10
Text 20
Text 2
Text 4
Text 5

folgendermaßen

Code:

Text
Text 1
Text 2
Text 3
Text 4
Text 5
Text 10
Text 20
Text X

Auch der Windows-Explorer sortiert seine Daten so.

Delphi-Quellcode:

//Sortiert Liste alphabetisch (beachtet dabei Zahlen nach Wert)
procedure BubbleSortExtra(List: TStrings; NumSort: Boolean = True);

    //Prüft auf Zahl im Strings, wie "Neuer Text (2)". Bei vorhanden sein
    //gibt StrB den Teil vor der Zahl, StrN die Zahl, StrE den Rest.
    function IsNumIn(Str: String; var StrB, StrNum, StrE: String): Boolean;
    var
      k: Integer;
    begin
      StrB := ''; // Text vor Zahl
      StrNum := ''; // Zahl
      StrE := ''; // Text nach Zahl

      k := 1;
      while k <= Length(Str) do
        if Pos(Str[k], '0123456789') = 0 then
        begin
          StrB := StrB + Str[k];
          Inc(k);
        end else Break;

      while k <= Length(Str) do
        if Pos(Str[k], '0123456789') > 0 then
        begin
          StrNum := StrNum + Str[k];
          Inc(k);
        end else Break;

      StrE := Copy(Str, k, Length(Str));
      Result := StrNum <> '';
    end;

var
  i: Integer;
  Done: Boolean;
  IsNum1, IsNum2: Boolean;
  StrTemp: String;
  StrB1, StrNum1, StrE1: String;
  StrB2, StrNum2, StrE2: String;
begin
  repeat //erste Sortierung; Strings nach Alphabet sortieren
    Done := True;
    for i := 0 to List.Count - 2 do
    begin
      if CompareText(List[i], List[i + 1]) > 0 then
      begin
        StrTemp := List[i + 1];
        List[i + 1] := List[i];
        List[i] := StrTemp;
        Done := False;
      end;
    end;
  until Done;

  if not NumSort then Exit;

  repeat //zweitete Sortierung; Strings mit Zahlen nach Höhe sortiert
    Done := True;
    for i := 0 to List.Count - 2 do
    begin
      IsNum1 := IsNumIn(List[i], StrB1, StrNum1, StrE1);
      IsNum2 := IsNumIn(List[i + 1], StrB2, StrNum2, StrE2);

      if (CompareText(StrB1, StrB2) = 0) and (IsNum1 and IsNum2) then
        if StrToIntDef(StrNum1, 0) > StrToIntDef(StrNum2, 0) then
        begin
          StrTemp := List[i + 1];
          List[i + 1] := List[i];
          List[i] := StrTemp;
          Done := False;
        end;
    end;
  until Done;
end; {Popov}

Bei der Sortierung handelt es sich um eine BubbleSort Funktion. Parameter NumSort = False erlaubt auch eine klassische Sortierung.

[Iwo Asnet]

Ich finde es eleganter, die Methode "CustomSort" einer TStringList zu nehmen und eine Ordnungsfunktion für die zu sortierenden Strings anzugeben.

Delphi-Quellcode:

program Project8;

{$APPTYPE CONSOLE}

uses
  Classes, SysUtils;

Var
  s : TStringList;

  Procedure SplitName (s : String; Var prefix : String; Var number : Integer; Var postfix : String);
  Var
    i,j : Integer;

  Begin
    prefix := '';
    number := 0;
    postfix := '';
    i := 1;
    while (i<=length(s)) and Not (s[i] in ['0'..'9']) do inc(i);
    prefix := Trim(Copy(s,1,i-1));
    j:=i;
    while (i<=length(s)) and     (s[i] in ['0'..'9']) do inc(i);
    if i>j then number := StrToInt(Copy(s,j,i-j));
    postfix := Trim(Copy(s,i,maxint));
  End;

  Function SortSmartFilenames(List: TStringList; Index1, Index2: Integer): Integer;
  Var
    s1,s2,q1,q2 : String;
    n,m : Integer;

  Begin
    SplitName(List[Index1],s1,N,s2);
    SplitName(List[Index2],q1,m,q2);
    result := CompareText(s1,q1);
    if result=0 then
      result := N-m;
    if result=0 then
      result := compareText(s2,q2);
  End;

begin
  s := TStringlist.Create;
  s.Add('Text');
  s.Add('Text 2');
  s.Add('Text 10');
  s.Add('Text 1');
  s.Add('Text 1 post');
  s.CustomSort(SortSmartFilenames);
  writeln(s.text);
  s.free;
  readln;
end.

[sx2008]

Das Sortierverfahren, bzw. die Reihenfolge in der sortiert wird nennt sich Natural Sort.
Man kann das Sortierproblem runterbrechen auf die Frage wie man zwei Strings vergleichen muss um sie in ihre "natürliche Reihenfolge" zu bringen.

siehe Code-Library: http://www.delphipraxis.net/29910-na...n-strings.html
Damit kann man dann auch das effizientere Quicksort anstelle dem langsamen Bublesort verwenden (wie Iwo Asnet schon gezeigt hat).

Die Methode CustomSort() verwendet intern ein Quicksort Algorithmus.

[Iwo Asnet]

Vielleicht sollte man dafür ein Kata eröffnen, denn die portierte Funktion ist ja grauenhaft (sie ist ja auch von C portiert und nicht adaptiert).

[Stevie]

Für XP/Server 2003 gibt's auch folgende Möglichkeit:

Delphi-Quellcode:

function StrCmpLogicalW(P1, P2: PWideChar): Integer;  stdcall; external 'Shlwapi.dll';
function NaturalCompare(List: TStringList; Index1, Index2: Integer): Integer;
begin
  Result := StrCmpLogicalW(PWideChar(List[Index1]), PWideChar(List[Index2]));
end;

Und dann am besten wie schon erwähnt in Verbindung mit CustomSort benutzen.

[DeddyH]

Müsste man dann aber nicht explizit nach PWideChar casten?

[Stevie]

Zitat von DeddyH:

Müsste man dann aber nicht explizit nach PWideChar casten?

Stimmt, hab die Delphi Versionen vor 2009 schon verdrängt Hab es mal editiert

[Iwo Asnet]

Zitat von Stevie:

Für XP/Server 2003 gibt's auch folgende Möglichkeit:

Ziemlich kompakt, würde ich sagen

[sx2008]

Wie auch immer man das NaturalCompare umsetzen mag, ich denke man sollte unbedingt ein Testprogramm dafür haben.
Rein gefühls- und erfahrungsmässig kann der NaturalCompare schwieriger sein als gedacht; vielleicht hat man irgendwelche Grenzfälle vergessen oder verhält sich bei manchen Strings anderst als gedacht.
Hier sind z.B. 4 Strings bei denen man etwas überlegen muss um sie in die richtige Reihenfolge zu bringen

Code:

Part- 200B
Part-200B
Part-01000-
Part-01000-000

PS:
function StrCmpLogicalW(P1, P2: PWideChar): Integer; stdcall; external 'Shlwapi.dll'; Gut, wenn's nicht immer funktioniert ist MS schuld

[himitsu]

Ach, daß könnt ihr alles vergessen ... in Windows 8 hat der Explorer das schon wieder vergessen.
Und wenn die aus Redmond konsequent sind, dann schaffen sie StrCmpLogicalW uch gleich mit ab.


Der sortiert jetzt auch nicht mehr nach 1 2 3 10 20 100, sondern 1 10 100 2 20 3