delphi - Delphi で StringList.Sort を安定した並べ替えに置き換えるにはどうすればよいですか?

Question

私は単純な StringList.sort を実行していますが、Delphi は安定した並べ替えではない QuickSort を使用しています。つまり、キーが等しいレコードの相対的な順序が変わる可能性があります。

安定したソートを使用する必要があります。これを実装する最も簡単な方法は何ですか?

---

Mike W's answer は、コードをあまり変更せずに行う最も簡単な方法かもしれません。

ありがとう、マイク。

Answer 1

文字列リストの Objects プロパティをまだ使用していない場合は、objects プロパティに元の位置を整数として格納するのが手っ取り早い方法です。その後、元の位置を考慮した独自の安定ソート比較関数を提供できます。独自のコードで行う必要があるのは、CustomSort を呼び出す直前に、objects プロパティを割り当ててリスト全体を反復処理することだけです。

function StableSortCompare(List: TStringList; Index1, Index2: Integer): Integer;
begin
  result := CompareStr(List[Index1], List[Index2]);
  if result = 0 then result := integer(List.Objects[Index1]) - integer(List.Objects[Index2]);
end;

procedure TSortTestForm.SortButtonClick(Sender: TObject);
var
  SL : TStringList;
  i : integer;
begin
  SL := TStringList.Create;
  try
    SL.AddObject('One', pointer(0));
    SL.AddObject('One', pointer(1));
    SL.AddObject('One', pointer(2));
    SL.AddObject('Two', pointer(3));
    SL.AddObject('Two', pointer(4));
    SL.AddObject('One', pointer(5));
    SL.AddObject('One', pointer(6));
    SL.AddObject('One', pointer(7));
    // SL.Sort; // Try instead of custom sort to see difference
    SL.CustomSort(StableSortCompare);
    for i := 0 to SL.Count-1 do begin
      Memo1.Lines.Add(Format('Text: %s Orig Pos: %d', [SL[i], integer(SL.Objects[i])]));
    end;
  finally
    SL.Free;
  end;
end;