AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Code-Bibliothek Neuen Beitrag zur Code-Library hinzufügen Intelligentes BubleSort; sortieren wie im Windows Explorer

Intelligentes BubleSort; sortieren wie im Windows Explorer

Ein Thema von Popov · begonnen am 17. Apr 2012 · letzter Beitrag vom 17. Apr 2012
Antwort Antwort
Seite 1 von 2  1 2   
Popov
(Gast)

n/a Beiträge
 
#1

Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 02:43
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.
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#2

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 05:22
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.
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#3

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 07:14
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.
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#4

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 08:08
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).
  Mit Zitat antworten Zitat
Benutzerbild von Stevie
Stevie

Registriert seit: 12. Aug 2003
Ort: Soest
3.842 Beiträge
 
Delphi 10.1 Berlin Enterprise
 
#5

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 09:44
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.
Stefan
“Simplicity, carried to the extreme, becomes elegance.” Jon Franklin

Delphi Sorcery - DSharp - Spring4D - TestInsight

Geändert von Stevie (17. Apr 2012 um 09:48 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.286 Beiträge
 
Delphi 11 Alexandria
 
#6

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 09:45
Müsste man dann aber nicht explizit nach PWideChar casten?
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von Stevie
Stevie

Registriert seit: 12. Aug 2003
Ort: Soest
3.842 Beiträge
 
Delphi 10.1 Berlin Enterprise
 
#7

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 09:48
Müsste man dann aber nicht explizit nach PWideChar casten?
Stimmt, hab die Delphi Versionen vor 2009 schon verdrängt Hab es mal editiert
Stefan
“Simplicity, carried to the extreme, becomes elegance.” Jon Franklin

Delphi Sorcery - DSharp - Spring4D - TestInsight
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#8

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 09:56
Für XP/Server 2003 gibt's auch folgende Möglichkeit:
Ziemlich kompakt, würde ich sagen
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#9

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 09:56
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu
Online

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.709 Beiträge
 
Delphi 10.4 Sydney
 
#10

AW: Intelligentes BubleSort; sortieren wie im Windows Explorer

  Alt 17. Apr 2012, 10:21
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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:43 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf