suche Hilfe für Abwandlung des Quicksort-Alg.

[iaby]

hallo zusammen,

mein problem ist folgendes:
ich habe eine playlist mit den einträgen:

• test1
  test2
  ...
  test10
  test11

wenn ich nun sortieren lasse, dann kommt sowas raus:

• test1
  test10
  test11
  ...

ich will aber das es dann so aussieht wie oben, also auch von den zahlen her richtig sortiert.
das alein wäre ja nicht das problem, aber wenn ich jetzt folgendes hab:

• 2test1
  2test2
  ...
  2test10

dann muss ich zuerst nach der einen zahl schauen, anschliessend noch die andere zahl vergleichen. wenn nun drei zahlen enthalten sind oder noch mehr, wirds dann immer komplizierter.

kurz gesagt, ich hab keinen plan wie ich das anstellen könnte!

hier mal mein quicksort source

Delphi-Quellcode:

procedure TPlaylistMain.quicksort(li_grenze, re_grenze: integer);
var li,re: integer;
    test, hilf: string;
begin
li:= li_grenze;
re:= re_grenze;
test:= lowercase(playlistview.Items[(li+ re) div 2].SubItems[0]);
repeat
  while lowercase(playlistview.Items[li].SubItems[0])< test do
    li:= li+1;
  while lowercase(playlistview.Items[re].SubItems[0])> test do
    re:= re-1;
  if li<= re then
    begin
    hilf:= playlistview.Items[li].SubItems[0];
    playlistview.Items[li].SubItems[0]:= playlistview.Items[re].SubItems[0];
    playlistview.Items[re].SubItems[0]:= hilf;
    li:= li+1;
    re:= re-1;
    end;
until li> re;
if li_grenze<re then quicksort(li_grenze,re);
if li<re_grenze then quicksort(li,re_grenze);
end;

weiß jemand rat und hat ne idee?
es müsste halt zuerst ein string so verglichen werden string1 > string2?
und dann strtoint(string1) > strtoint(string2)?
aber wie solch ich das umsetzen, wenn es mehrere zahlen und strings ineinander kombiniert sind?
das ist eben mein prob.

ich hoffe ihr habt meine frage verstanden ;-)

gruss,
iaby

[IngoD7]

Achtung Schnellschuß als Ansatz (vielleicht gibt es besseres):
Ich würde den String aufschlüsseln in seine unterschiedlichen Kriterien. Und die dann nacheinander sortieren, also erst alle Sätze nach dem wichtigsten Kriterium sortieren, dann innerhalb einer jeden Kriteriumgruppe nach dem zweitwichtigsten Kriterium sortieren, usw. (ich hoffe, du verstehst vom Prinzip her, was ich meine).

Alles in einem Quicksort-Durchgang zu erschlagen ist wohl nicht so einfach.

[Phoenix]

Tja, da gibts keine Musterlösung für.

Es geht hier ja um playlists, also gehe ich einfach mal davon aus, das die Listen zum sortieren zum Teil auch aus Dateinamen gebildet werden, ja?

Ich habe da eine Idee, die ist aber wahrscheinlich nicht ganz so schnell umzusetzen.

1.) Du trennst Nummern von Strings.
Will heissen: Du gehst jeden Eintrag der Liste (ggf. sogar direkt am Dateinamen!) zeichen für zeichen durch, und wenn Du eine Änderung von Nummer auf Zeichen oder umgekehrt bemerkst, fügst Du ein Trennzeichen ein. Das µ hat sich hier für mich bewährt, da es a) auf der Tastatur noch leicht zu finden ist und b) fast nie in der freien Wildbahn vorkommt.

2.) Danach gehst Du beim sortieren her, und sortierst verschachtelt für jede Ebene µ's.

Beispiel:

Code:

1µTitel_µ15
3µTitelµ4
1µTitelµ1

wird erst zu:

Code:

1µTitel_µ15
1µTitelµ1
3µTitelµ4

und dann zu:

Code:

1µTitelµ1
1µTitel_µ15
3µTitelµ4

Also immer einen Bereich nach dem anderen sortieren.
Die Bereiche findest Du dann ja mit strpos recht einfach raus, weil die zu 99,999999999% kein fremdes µ da reinrutscht.

[negaH]

Du zerlegst die Strings in Zahlen, wobei alle Buchstaben zwischen den Zahlen eben Seperatoren sind.
Es entsteht also pro Strings ein Array aus Zahl,Text,Zahl,Text,Zahl,Text usw. usw.
Davon hast du in der Quicksort Routine ja zwei Arrays und nun fängst du an diese beiden Arrays und deren Elemente zu vergleichen. Aussehen könnte das ja dann so

Delphi-Quellcode:

type
  TElement = packed record
    Zahl: Integer;
    Text: String;
  end;

  TElementArray = array of TElement;

function ExtractElements(const Value: String): TElementArray;
var
  Text: PChar;
  Count: Integer;
  IsNumber,WasNumber,IsFirst: Boolean;
begin
  Result := nil;
  Text := PChar(Value);
  if Text <> nil then
  begin
    Count := -1;
    WasNumber := False;
    IsFirstChar := True;
    while Text^ <> #0 do
    begin
      IsNumber := Text^ in ['0'..'9'];
      if (IsNumber <> WasNumber) or IsFirstChar then
      begin
        WasNumber := IsNumber;
        IsFirstChar := False;
        Inc(Count);
        if Count mod 16 = 0 then SetLength(Result, Count + 16);
      end;  
      if IsNumber then Result[Count].Zahl := Result[Count].Zahl * 10 + Ord(Text^) - Ord('0')
        else Result[Count].Text := Result[Count].Text + Text^;
      Inc(Text);
    end;
    SetLength(Result, Count);
  end;
end;


function CompareElements(const A,B: TElementArray): Integer; 
  
  function Min(A,B: Integer): Integer;
  begin
    if ALen <= BLen then Result := ALen
      else Result := BLen;
  end;

var
  I,ALen,BLen: Integer;
begin
  Result := 0;
  ALen := High(A);
  BLen := High(B); 
  for I := 0 to Min(ALen, BLen) do
  begin
    Result := A[I].Zahl - B[I].Zahl;
    if Result <> 0 then Exit;
    Result := AnsiCompareText(A[I].Text, B[I].Text);
    if Result <> 0 then Exit; 
  end;
  Result := ALen - BLen;
end;

Mit ExtractElements() werden erstmal beide zu vergleichende Strings in Zahl/String Elemente umgewandelt und dann diese Arrays mit CompareElements() verglichen. Gibt diese Funktion < 0 zurück so ist A < B, bei 0 ist A == B und bei A > B eben > 0.

Obiger Code ist natürlich nur ein vereinfachter Vorschlag. Man könnte auch gleich die beiden Strings so wie oben gezeigt in parallel umwandeln und deren Resultate sofort vergleichen. Das hätte den Vorteil das schon sehr frühzeitig der Konvertierungscode abgebrochen werden kann.

Gruß Hagen

[iaby]

ich danke euch einmal rechherzlich!

werde mir das wohl noch genauer anschauen müssen und ne gute routine überlegen.
werde mich wohl nochmal melden ;-)

gruss,
iaby