TOPページへ戻る  PCページへ戻る  一覧へ戻る

TListを使った整列

数値配列の整列 〜QuickSort〜」では、配列にTSortArrayという 動的配列を定義して使いました。そこで、ここではTListを使ったソートを紹介します。

自前でTList用のソートを作ってみましょう。 これは、TList用に「数値配列の整列 〜QuickSort〜」で紹介した コードを修正するだけです。下のようになります。


unit QSort;

interface

USES Classes;

type
  TSorts = class(TObject)
    destructor Destroy;reintroduce;
  public
    procedure QuickSort(Val:TList;start,last:integer);
  end;

implementation

destructor TSorts.Destroy;
begin
inherited Destroy;
end;

procedure TSorts.QuickSort(Val:TList;start,last:integer);
var i,		// while文のカウンタ、比較対象位置を示す
    j,		// 入れ替え位置を示すカウンタ
    x,		// 入れ替え用の一時変数
    y:integer;	// 比較対象の値を格納する変数
begin						// TListがDoubleの場合、黄色のIntegerをDoubleに変えるだけ
j := (start + last) div 2;			// 配列の中央をjに格納
x := Integer(Val[start]^);			// 配列の中央の値と最初の値を交換
Integer(Val[start]^) := Integer(Val[j]^);
Integer(Val[j]^) := x;
y := Integer(Val[start]^);			// 基準値をyに代入
j := start + 1;					// 入れ替え位置を設定
i := start + 1;					// 比較対象位置を設定
while i <= last do
    begin
    if Integer(Val[i]^) < y then      	// 降順に整列するときは < を > にする
        begin
        x := Integer(Val[i]^);
        Integer(Val[i]^) := Integer(Val[j]^);
        Integer(Val[j]^) := x;
        Inc(j);					// 入れ替えがあったら入れ替え位置をインクリメント
        end;
    Inc(i);
    end;
Dec(j);						// 最後の入れ替えでインクリメントされた分をデクリメント
x := Integer(Val[start]^);			// 最後の入れ替え位置の数と基準値を入れ替え
Integer(Val[start]^) := Integer(Val[j]^);
Integer(Val[j]^) := x;
if j-start > 1 then				// 配列の開始位置と入れ替え位置の差が1より大きい場合
    QuickSort(Val,start,j);			// クイックソート(自分自身)をstartからjまで実施
if last-j > 1 then				// 配列の終了位置と入れ替え位置の差が1より大きい場合
    QuickSort(Val,j+1,last);			// クイックソート(自分自身)をj+1からlastまで実施
end;

end.

コードの説明

上のコードでは、TListのItemには整数(Integer)が格納されているとします。 但し、もう少し正確にいうと、Itemに格納されているのは整数のポインタです。 そのため、TList型変数valの各要素をIntegerで型キャストしています。TListの要素がDoubleの場合、 Doubleで型キャストしてください。

QuickSort手続きの引数がTSortArray型からTList型に変わっています。TList型は Classesユニットを必要とするため、QuickSort手続きの前にUSES節を設けてClassesユニットを 指定しています。

TOPページへ戻る  PCページへ戻る  一覧へ戻る