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:

Zitat von DeddyH (Beitrag 1162214)

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:

Zitat von Stevie (Beitrag 1162212)

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

Ziemlich kompakt, würde ich sagen :stupid:

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

Delphi-Quellcode:

function StrCmpLogicalW(P1, P2: PWideChar): Integer; stdcall; external 'Shlwapi.dll';

Gut, wenn's nicht immer funktioniert ist MS schuld :wink:

[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. :roll:


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

[Stevie]

Zitat:

Zitat von himitsu (Beitrag 1162227)

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

Welche Sortierung der Explorer benutzt, ist durch einen Registry Eintrag geregelt, den konnte man schon mindestens unter Vista verstellen afaik.

[Iwo Asnet]

Super, damit ist die Lösung zwar kompakt, aber i.A. nicht das, was man will.

Ich wäre ja dafür, die Idee von Popov aufzugreifen, nach dem ein zu sortierender Schlüssel aus den Bestandteilen:
<Prefix><Zahl><Postfix> besteht, wobei jedes Teil optional ist. Die 'Teile' werden von links nach rechts vergleichen, wobei führende und folgende Leerzeichen ignoriert werden. Wer will, kann bei Gleichheit der Einzelkomponenten noch die Strings in Gänze vergleichen, um eine totale Ordnung zu erzielen.

Zitat:

Zitat von sx2008 (Beitrag 1162217)

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

Das wäre dann

Code:

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

Kann man mit leben, finde ich.

[Delphi-Laie]

Zitat:

Zitat von himitsu (Beitrag 1162227)

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. :roll:


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

Ist zwar völlig außerhalb des eigentlichen Diskussionsthemas, aber: Es gibt ein Bild, das die Menschwerdung zeigt: Aus mehr oder weniger krummbuckeligen Ur-/Früh-/Altmenschen (Australopithecus, Homo erectus, Homo habilis, Homo (sapiens) neanderthalensis usw.) wird ein aufrechtgehender steinzeitlicher Zweibeiner (Cro-Magnon, Homo sapiens sapiens). Doch der sinkt und krümmt sich allmählich wieder zusammen, als zunächst die Kraft- und Arbeitsmaschinen ihm helfen, und vollends, als er letztlich nur noch vor der Informationsverarbeitungsmaschine (dem Computer) kauert (hoffentlich ergeht es uns allen nicht auch einmal so).

Und dies als Metapher in der Erinnerung, kommt mir Windows in seinen verschiedenen Versionen auch vor - es wird immer schlimmer!

Popov, Dein "intelligent" löste bei mir Hoffnungen aus, die sich nicht erfüllten. Intelligent ist also nicht der Algorithmus i.S. eines effizienten Laufzeitverhaltens, sondern beim Vergleichen. Auch ich rege an, einen laufzeitgünstigeren Sortieralgorithmus zu verwenden.

[Stevie]

Zitat:

Zitat von Iwo Asnet (Beitrag 1162253)

Super, damit ist die Lösung zwar kompakt, aber i.A. nicht das, was man will.

Nun, da das Thema heißt "sortieren wie im Windows Explorer", ist die Function StrCmpLogicalW genau das Richtige, denn diese wird vom Explorer benutzt.

Dass die Sortierung anhand bestimmter Pattern eventuell anders sein muss, steht auf einem anderen Blatt.