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

数値配列の整列 〜QuickSort〜

数値を並べ替えるアルゴリズムはいくつかありますが、最も高速と言われるのが クイックソートです。ここではクイックソートのアルゴリズムとそのコードを示します。

クイックソートのアルゴリズムを端的に言うならば、基準値の大小で分けていくこと を繰り返すというものです。下の9つの数値で具体的に示します。

(6 9 4 5 7 3 8 0 2)

最初にこの数値の中から1つ選び(=基準値)、それより大きいグループと小さいグループに 分けます。ここでは中央の数値7を基準値にしました。

(6 9 4 5  3 8 0 2)

次に、基準値を先頭の数値と入れ替えます。

 9 4 5 6 3 8 0 2)

2番目以降の数値(ここでは9)を基準値(ここでは7)と比較します。基準値より小さい場合、2番目以降の 数値(ここでは9)と入れ替えます。入れ替えがあった場合、入れ替える位置を1つ大きくします。
 具体的にどのように数値が移動するか、例で説明します。 下の例では、が基準値、 が比較対象の数値、 が入れ替える場所の数値です。 比較対象と入れ替え先が同じ場合、で表しています。

  4 5 6 3 8 0 2)
    ↓9>なので、比較対象を1つ右へ

   5 6 3 8 0 2)
    ↓4<なので、4と9を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4   6 3 8 0 2)
    ↓5<なので、5と9を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4 5   3 8 0 2)
    ↓6<なので、6と9を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4 5 6   8 0 2)
    ↓3<なので、3と9を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4 5 6 3   0 2)
    ↓8>なので、8>なので、比較対象を1つ右へ

 4 5 6 3  8  2)
    ↓0<なので、0と9を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4 5 6 3 0  9 
    ↓2<なので、2と8を入れ替えて、比較対象と入れ替え位置を1つ右へ

 4 5 6 3 0  9 8)

比較が終了したら、基準値と入れ替え位置の数値を入れ替えます。

 4 5 6 3 0  9 8)

上の状態では、基準値()から右の数値が 基準値以上になっています。そこで、0と7の間で2つの グループ(2 4 5 6 3 0)と(7 9 8)に分け、それぞれに上と同じ操作を繰り返します。 ここでは、(2 4 5 6 3 0)を例に示します。

まず、基準値を中央の6にします。

(2 4 5  3 0)

先頭の数値(2)と基準値()を入れ替えます。

 4 5 2 3 0)

2番目の数値から基準値と比較して入れ替えていきます。

  5 2 3 0)
    ↓4<なので、自分自身と入れ替えて比較対象、入れ替え位置を1つ右へ

 4  2 3 0)
    ↓5<なので、自分自身と入れ替えて比較対象、入れ替え位置を1つ右へ

 4 5  3 0)
    ↓2<なので、自分自身と入れ替えて比較対象、入れ替え位置を1つ右へ

 4 5 2  0)
    ↓3<なので自分自身と入れ替えて比較対象、入れ替え位置を1つ右へ

 4 5 2 3 
    ↓0<なので、自分自身と入れ替えて終了。
     最後に比較対象と入れ替え位置の数値を入れ替える。

 4 5 2 3 

上のように整列したら、前回同様に比較対象の前後で再びグループ分けして繰り返して行きます。 上の場合、グループは(0 4 5 2 3)と(6)になります。
これをコードにすると、下のようになります。


unit QSort;

interface

type 					//整数の配列を定義
  TSortArray = array of Integer;	//整数ではない場合は型を変えればOK
  
procedure QuickSort(Val:TSortArray;start,last:integer);	//クイックソート本体

implementation

procedure QuickSort(Val:TSortArray;start,last:integer);
var i,		// while文のカウンタ、比較対象位置を示す
    j,		// 入れ替え位置を示すカウンタ
    x,		// 入れ替え用の一時変数
    y:integer;	// 比較対象の値を格納する変数
begin
j := (start + last) div 2;	// 配列の中央をjに格納
x := Val[start];		// 配列の中央の値と最初の値を交換
Val[start] := Val[j];
Val[j] := x;
y := Val[start];		// 基準値をyに代入
j := start + 1;			// 入れ替え位置を設定
i := start + 1;			// 比較対象位置を設定
while i <= last do
    begin
    if Val[i] < y then   	// 降順に整列するときは < を > にする
        begin
        x := Val[i];
        Val[i] := Val[j];
        Val[j] := x; 
        Inc(j);			// 入れ替えがあったら入れ替え位置をインクリメント
        end;
    Inc(i);
    end;
Dec(j);				// 最後の入れ替えでインクリメントされた分をデクリメント
x := Val[start];		// 最後の入れ替え位置の数と基準値を入れ替え
Val[start] := Val[j];
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.

コードの説明

クイックソートをUnitとして作成しています。 そのため、他のアプリケーション作成の際にも使えます。 その使い方は、新規作成→ユニットを選択し、新しいUnitに上のコードを丸ごとコピーして QSort.pasという名前で保存します。また、クイックソートを使うユニットのUSES節に QSortを追加するだけです。

最初の説明でイメージをつかめていれば、コードのコメント文を読むとほとんど分かると思います。 クイックソート関数の特徴は、自分自身を関数の中で呼び出しているところです。 このような関数は再帰関数と呼ばれ、配列を整列する関数によく見られます。上のコードでは、 グループ分けした各グループの要素が3つ以上の場合に再帰的に呼び出すようになっています。 要素が2つ以下の場合、整列済みなので呼び出す必要はありません。要素が2つ以下の場合、 なぜ整列済みになるかは3つの要素でやってみると分かります。 (入れ替える場所の数は必ず基準値より小さいためです)

通常の関数では、引数の値を関数中で変えても関数を抜けると元の値に戻って しまいます。これでは再帰的に呼び出してもちゃんと整列してくれません。 そこで、関数中で引数の値を変えられるよう、ポインタとして渡すようにします。 Delphiでは、独自の型を定義してそれを関数の引数とした場合、ポインタを渡すことになります。 コードの最初の方で配列をわざわざ独自の型にしているのはそのためです。 TSortArray型を定義せず、QuickSort関数でval:array of Integerと宣言してもちゃんと整列できないのです。

再帰関数では、下手をすると無限ループに陥る可能性があります。上のコードの最後の4行で 無限ループにならないようにしています。すなわち、要素が2つ以下のグループに細分化 された時点で終了します。

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