Spaltengenau sortieren

[Bjoerk]

Ich muß zum Beispiel das Wort NOTEBOOK so sortieren, daß die Reihenfolge doppelt vorkommender Buchstaben erhalten bleibt. Hier also 54812673. Ein herkömmliches stabiles Sortierverfahren berücksichtigt das nicht (weil O eben O). Ich brech mir dabei grad einen ab. Hat jemand eine bessere Idee? (Die Indices (Dest) brauch ich im Programm später).

Delphi-Quellcode:

function MinCharPos(const S: string; const NoChar: char): integer;
var
  MinChar: Char;
  I, J: integer;
begin
  Result := 0;
  MinChar := NoChar;
  for I := 1 to Length(S) do
    if S[I] <> NoChar then
    begin
      MinChar := S[I];
      Break;
    end;
  if MinChar <> NoChar then
  begin
    for I := 1 to Length(S) do
      for J := 1 to Length(S) do
        if (I <> J) and (S[I] <> NoChar) and (S[I] <= MinChar) then
          MinChar := S[I];
    for I := Length(S) downto 1 do
      if S[I] = MinChar then
        Result := I;
  end;
end;

procedure SortByKey(const S, Key: string; Dest: TIntegerList); // Spaltengenau sortieren;
var
  TempKey: string;
  I, J: integer;
begin
  Dest.Clear;
  if (Length(Key) > 0) and (Length(Key) = Length(S)) then
  begin
    for I := 0 to Length(Key) do
      Dest.Add(0);
    TempKey := Key;
    for I := 1 to Length(TempKey) do
    begin
      J := MinCharPos(TempKey, Char(254));
      Dest[I] := J;
      TempKey[J] := Char(254);
    end;
  end;
end;

[DSP]

Was meinst du mit der Reihenfolge von doppelten Buchstaben und weshalb sollte O nicht gleich O sein?

Grüsse
DSP

[Sir Rufo]

Er mochte, dass das erste O vor dem zweiten O und das vor dem dritten O in der Sortierung bleibt. Damit habe ich eigentlich schon den entscheidenen Hinweis geliefert

BTW Ist die Angabe der Reihenfolge 54812673 bewusst falsch, oder nur vertippt?

[jfheins]

Zitat von Bjoerk:

Ich muß zum Beispiel das Wort NOTEBOOK so sortieren, daß die Reihenfolge doppelt vorkommender Buchstaben erhalten bleibt. Hier also 54812673. Ein herkömmliches stabiles Sortierverfahren berücksichtigt das nicht (weil O eben O).

Das ist doch gerade DAS Merkmal eines stabilen Sortierverfahrens: Elemente, die "gleich" sind, bleiben in der Eingabereihenfolge.

[Bjoerk]

Ja. Sorry.

Code:

NOTEBOOK
12345678

BEKNOOOT
54812673

[DSP]

Der Sinn erschliesst sich mir nicht, weshalb braucht man unbedingt 1101 wenn es ein 1101 ebenfalls tut resp identisch ist? Ansonsten wüsste ich nicht, warum ein Stabiles Sortierverfahren plötzlich instabil werden sollte, das ist aber ein anderes Thema. Ansonsten gibt es ja noch die Möglichkeit ein eigenes Sortierfeld zu deklarieren und dieses nach belieben bestückt, bspw wo bestimmte Sequenzen durch Token getauscht werden.

Grüsse
DSP

[mkinzler]

Zitat:

Der Sinn erschliesst sich mir nicht, weshalb braucht man unbedingt 1101 wenn es ein 1101 ebenfalls tut resp identisch ist?

Z.B. wegen den Werten in den weiteren Spalten.

[DSP]

Weshalb willst du denn einzelne Spalten nicht sortieren?

Da kannst dir die Sortiererei gkeich ganz sparen, ... ansonsten halt eine Skiptabelle mit inplementieren, damit du gezielt einzellne Spalten überspringen kannst.

<verwundert>

[Uwe Raabe]

Zitat von Sir Rufo:

BTW Ist die Angabe der Reihenfolge 54812673 bewusst falsch, oder nur vertippt?

Zitat von Bjoerk:

Ja. Sorry.

Code:

NOTEBOOK
45821673

Habe ich da was nicht richtig verstanden?

Delphi-Quellcode:

NOTEBOOK
12345678

54812673
BEKNOOOT

Alternativer Code (der Sinn des Parameters S erschließt sich mir nicht ganz):

Delphi-Quellcode:

procedure SortByKey(const Key: string; Dest: TIntegerList);
var
  Ch: Char;
  I: Integer;
  LastKey: Char;
  MinKey: Char;
  MinPos: Integer;
begin
  Dest.Clear;
  LastKey := #0;
  while Dest.Count < Length(Key) do begin
    { suche kleinsten, der größer als LastKey ist, und speichere in MinKey. }
    MinPos := 0;
    for I := 1 to Length(Key) do begin
      Ch := Key[I];
      if (Ch > LastKey) and ((MinPos = 0) or (Ch < MinKey)) then begin
        MinKey := Ch;
        MinPos := I;
      end;
    end;
    { Position anfügen }
    Dest.Add(MinPos);
    { das wird unser neuer LastKey }
    LastKey := MinKey;
    { alle folgenden Positionen anfügen, die gleich LastKey sind }
    for I := MinPos + 1 to Length(Key) do begin
      if Key[I] = LastKey then begin
        Dest.Add(I);
      end;
    end;
  end;
end;

[Bjoerk]

So isses. Weil nacher weitere strings der gleichen Länge danach sortiert werden. So geht’s z.B. eben nicht.

Delphi-Quellcode:

    for I := 1 to Length(TempKey) - 1 do
      for J := I + 1 to Length(TempKey) do
        if TempKey[I] > TempKey[J] then
        begin
          C := TempKey[I];
          TempKey[I] := TempKey[J];
          TempKey[J] := C;
          Dest.Exchange(I, J);
        end;