この発言に対し以下のコメントが寄せられています

#00307　べあ            さん　RE:マージソート修正








便宜上、TListを継承したクラスを想定しています。

procedure TXXXList.Sort(Comp:TListSortCompare);
var Size :integer;
    Tmp  :PPointerList;
  procedure InsertionSort(First,Last:Integer);//たぶん挿入ソート
  //安定、遅い
  var i,J:Integer;
      T  :Pointer;
  begin
    for I := First + 1 to Last do begin
      T := List^[I];
      J := i;
      while (J > First) and (Comp(List^[J-1],T) > 0) do Dec(J);
      System.Move(List^[J],List^[J+1],(i - j) * SizeOf(Pointer));
      List^[J] := T;
    end;
  end;

  procedure QuickSort(First,Last:Integer);//クイックソート  
  //安定でない、速い、スタックを大量消費
  var
    I, J: Integer;
    T   : TPointer;
  begin
    repeat
      I := First;
      J := Last;
      P := List^[(I + J) div 2]);
      repeat
        while Comp(List^[I],T) < 0 do Inc(I);
        while Comp(List^[J],T) > 0 do Dec(J);
        if I <= J then
        begin
          Exchange(I, J);
          Inc(I);
          Dec(J);
        end;
      until I > J;
      if First < J then QuickSort(First, J);
      First := I;
    until I >= Last;
  end;

  procedure MergeSort(First,Last: Integer);//マージソート
  //安定、速い、メモリ、スタックを大量消費
  var I,J,K,P,Mid:Integer;
  begin
    if First{+ 20} < Last then begin
      Mid :=(First + Last) div 2;
      MergeSort(First,Mid);
      MergeSort(Mid+1,Last);
      P := 0; //作業領域のインデックス
      for I:=first to Mid do begin
        Tmp^[P] := List^[i];
        Inc(P);
      end;
      i := Mid + 1; J :=0 ; k := first;
      while (i <= Last) and (J < P) do
        if Comp(Tmp^[J],List^[I]) > 0
          then begin
            List^[k] := List^[i];
            Inc(k);Inc(i);
          end else begin
            List^[k] := List^[j];
            Inc(k);Inc(J);
          end;
      while j < P do begin
        List^[K] := Tmp^[j];
        inc(k);inc(j);
      end;
    end;// else InsertionSort(First,Last); //スタック節約なら
  end;
begin
  if FCount > 1 then
    case SortType of
      stInsertion:InsertionSort(0,count-1);
      stQuick    :QuickSort(0,count-1);
      stMerge    :begin
                    GetMem(Tmp,(count div 2 + 1) * SizeOf(Pointer));
                    try
                      MergeSort(0,FCount-1);
                    finally
                      FreeMem(Tmp);
                    end;
                  end;
    end;
end;


ソートの用語
・キー　順序を決定する要素。　
・安定　同じキーの値を持つ項目の順序関係が、ソートの前後で入れ替わらない。


                       97/12/07(日) 19:09 べあ(BYI15773)

Original document by べあ            氏 ID:(BYI15773)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。