StringGrid でソートをしたい(2)

さて、前回に引き続いてソートの話です。
前回の終わりで、QuickSort は不安定なソートなので問題があるという話をしました。
では、どんなときに問題があるのかを説明します。

まあ、こんなデータがあったとします。
この時に、Number でソートしてあって、同じ Number の行は Total でソートしてあって欲しいといわれたらどうでしょうか？
QuickSort で作った場合、これは出来ますか？
やろうと思ったら、Number でソートした後、同じ Number の列だけを Total でそれぞれソートをかけるなどというスマートでない手を使うことになります。
ところが、安定なソートの場合は Total でソートした後、Number でソートするだけで終わりです。
キーソートにおいては、安定なソートの方が便利なことが多いのです。

以下に安定なソートの代表格である MergeSort を使ったコード例を示します。

procedure TForm1.Sort(ACol: Integer);
  procedure MergeSort(Buffer: TStringList; ARow, Count: Integer);
  var
    I, J: Integer;
    Center: Integer;
    Temp: TStringList;
  begin
    if Count = 1 then Exit;

    Center := Count div 2;

    MergeSort(Buffer, ARow, Center);
    MergeSort(Buffer, ARow + Center, Count - Center);

    I := 0;
    J := 0;
    Temp := TStringList.Create;
    while (I < Center) and (J < Count - Center) do
    begin
      if CompareStr(Buffer[ARow + I], Buffer[ARow + Center + J]) > 0 then
      begin
        Temp.AddObject(Buffer[ARow + Center + J], Buffer.Objects[ARow + Center + J]);
        Inc(J);
      end
      else
      begin
        Temp.AddObject(Buffer[ARow + I], Buffer.Objects[ARow + I]);
        Inc(I);
      end;
    end;

    if I = Center then
      while J < Count - Center do
      begin
        Temp.AddObject(Buffer[ARow + Center + J], Buffer.Objects[ARow + Center + J]);
        Inc(J);
      end
    else
      while I < Center do
      begin
        Temp.AddObject(Buffer[ARow + I], Buffer.Objects[ARow + I]);
        Inc(I);
      end;

    for I := 0 to Count - 1 do
    begin
      Buffer[ARow + I] := Temp[I];
      Buffer.Objects[ARow + I] := Temp.Objects[I];
    end;

    Temp.Free;
  end;

var
  ARow: Integer;
  Buffer: TStringList;
begin
  with StringGrid1 do
  begin
    Buffer := TStringList.Create;

    //Buffer に key とそれに対応する Rows を格納する
    for ARow := TopRow to RowCount - 1 do
    begin
      Buffer.AddObject(Cells[ACol, ARow], TStringList.Create);
      TStringList(Buffer.Objects[ARow - TopRow]).Assign(Rows[ARow]);
    end;

    //Buffer を実際にソートする
    MergeSort(Buffer, 0, RowCount - TopRow); //Buffer.Sort; と置き換え

    //ソートしたデータを Grid に書き戻す
    for ARow := TopRow to RowCount - 1 do
    begin
      Rows[ARow].Assign(TStringList(Buffer.Objects[ARow - TopRow]));
      TStringList(Buffer.Objects[ARow - TopRow]).Free;
    end;

    Buffer.Free;
  end;
end;

基本的に、前のソースのソート部分をマージソートに置き換えただけです。
マージソート部分のアルゴリズムは、アルゴリズム本にいくらでも載っているのでそれを見てください。
ただ、マージソート部分のソースコードは自分的には汚いように見えて気に食いません。
誰かきれいに書けたという方がいましたら、コードを送ってください。
私もきれいだと思ったら、名前入りで(匿名も可)ここのソースと差し替えさせていただきます。

Return index page