クイック整列法(整列法3)

 整列法(Sort)は,アルゴリズムの中でも最も基本的なものので,多くの研究がされ色々な整列法が開発されています。ここではその中でも 最も代表的な整列法であるクイック整列法を紹介します。 クイック整列法はクイックソートと英語のままで呼ばれることが多いので,以下では,クイックソートと言うことにします。

 この整列法は1960年 C.A.R. Hoareによって発明された整列法です。平均的には最も高速な方法ということで,クイックソートと呼ばれ,現在最もよく使われる整列法です。

状況設定

  選択整列法の場合と同じ状況を考えましょう。すなわち,ランダムに与えられた,文字列を辞書順に整列することを考えます。

 簡単にためのアルファベットからなる10個文字列が与えられ,それを辞書順の整列することを考えます。(住所録で名前順に整列する場合も同様です。)

 実際は1000個の文字列でも全く同様に動作します。


 与えられた文字列が配列変数で D$(1), D$(2), ..., D$(10) と与えられたとします。この中身を入れ替えて,辞書順に D$(1), D$(2), ..., D$(10) を作ります。例えば,

D$(1)= "cxjh"   D$(1)= "abyxxxe"  
D$(2)= "js"   D$(2)= "cbyb"  
D$(3)= "abyxxxe"   D$(3)= "cxjh"  
D$(4)= "mvcbjx"   D$(4)= "ekoq"  
D$(5)= "tlxvyvn"   D$(5)= "js"  
D$(6)= "p" が与えられたとき, D$(6)= "mvcbjx" とする
D$(7)= "n"   D$(7)= "n"  
D$(8)= "twvo"   D$(8)= "p"  
D$(9)= "ekoq"   D$(9)= "tlxvyvn"  
D$(10)= "cbyb"   D$(10)= "twvo"  

ということです。

アイデア

  クイックソートは,まず,全体データを適当に処理して,次のようにします。

 まず適当に,あるデータPを取ります。このデータが最終的にどこに来るか決め,それを基点として,左右に2つに分けて,右側のデータはすべて,P以上,左側のデータはすべてP以下であるように する。つまり,

          Pの右データ
        P
Pの左データ

Pの左側のデータ≦P≦Pの右側のデータ

であるようにします。

 この処理を Partition と呼びましょう。この処理が一般的に得られたとすると,クイックソートQSort は左データ,右データについて同様なことを行うことで全体を整列するものです。


 この Partition を認めるとQSort は再帰的表現を使って次のように簡単に書けます。(説明のため行番号を付けています。)

01 Sub QSort(left,right)
02    if left < right then
03       p = Partition(left, right)
04       Call QSort(p+1, right)
05       Call QSort(left, p-1)
06    end if
07 End Sub

ここで,QSort(left,right)は D$(left) とD$(right) の間のデータをクイックソートで整列することを示します。

 1行目は,Sub 宣言です。 QSort(left,right) と宣言しています。

 2行目は,終了判定です。 left = right になったら,データが一個ですから,終わりです。それ以外は以下の処理を行います。

 3行目で,Partition(left,right) を行います。このPartition(left,right)はleft とright の間のデータを分割するということ示しています。 p=Partition(left,right) はその結果Pの位置を返しています。

 4行目では,Partition の結果,右側となったデータを更に QSort で整列するという再起呼び出しを行っています。

 5行目では,Partition の結果,左側となったデータを更に QSort で整列するという再起呼び出しを行っています。


 このように,QSort の本質的部分は Partition と言えます。そこで次にこのPartition について説明しましょう。

Partition の実際

 この操作Partitionは例えば次のようにすると実現されます。

  1. 適当にデータPを取ります。
  2. Pをとりあえず,左端に移します。
  3. Pの右隣から順次,データを調べて,P以下のデータがあったら,それを,左データの組に入れ,P以上のデータがあったら,右データの組に入れます。
  4. 最後にPを左データの組と右データの組の間にPを入れます。

 ここで,3の処理をもう少し具体的に表してみます。

  • まず最初は左データの組は空であるとします。
  • 左データの組に入るデータがあったら,Pの隣から順次埋めていきます。
  • その際,左データの組の個数を数えながら操作を行って行きます。
  • そうすると,左データが現れたとき,埋める位置がその個数から分かります。
  • 最後まで調べ終わったとき,左データの組に入っていないものは,右データの組に入ります。
  • そこで,その境目(それは右データの個数から分かります)にPを移動して操作が終わります。

以上の操作をプログラムで表してみると次のようになります。(説明のため行番号を付けています。)

01 Function Partition(left,right)
02    Call Change(left, Int((left+right)/2))
03    last = left
04    for i= left + 1 to right
05       if (D$(i) < D$(left)) then 
06          last = last + 1
07          Call Change(last,i)
08       end if
09    next i
10    Call Change(left,last)
11    Partition = last
12 End Function 

ここで,使われている Change(,a,b) は D$(a) と D$(b) を交換する処理を表しています。


1行目は関数宣言です。この操作を Partition(left,right) という関数で表します。これはleftから right の間にあるデータについてその操作を行うことにして,データPの位置を関数の値として,返します。

2行目はPを取っています。原理的にはどれでも良いですが,ここではPとして中央にあるデータを取り,それを左端に置きます。

3行目の last はPが最終的に置かれる位置を求めるための変数です。last - left がPの左データの個数を表します。最初は last - left = 0 です。

4行目から9行目までが,データをPの左右に分ける部分です。

5行目で,もしD$(i) < D$(left)なら, D$(i) はPの左にあるデータです。そこでこの場合,Pの左に置きますから,Pの最終的位置は1だけ右に移動します。これが6行目の, last = last + 1です。7行目の Change(last,i) はそのデータをlast の位置に入れ替えています。左端に取りあえず置いたP以外,last の位置より左にあるデータがPの左データになっています。

4行から9行が終わった時点で,left+1から last の位置にあるデータがPの左データです。ですから,10行で左端に取りあえず置いたPと last の位置にある データを入れ替えると,操作が終わることになります。11行ではlastを関数値として返しています。


 この操作を実際の簡単な場合に実行してみましょう。見易さのためデータは数とします。

1 2 3 4 5 6 7 8 9 10
10

 とデータが並んでいたとします。上段は i を表し,下段は D$(i) を表しています。

このデータに対して,p=Partition(1,10) を実行してみましょう。

1.Pの決定:中央値としてPを取ります。D$(5)="6"がPです。

1 2 3 4 5 6 7 8 9 10
10

2.Pを左端に移動:1と5を入れ替えます。

1 2 3 4 5 6 7 8 9 10
10

last=1

3.i=2から処理を始めます。黄色が左データ

i=2

1 2 3 4 5 6 7 8 9 10
10

last=2


i=3

1 2 3 4 5 6 7 8 9 10
10

last=3


i=4

1 2 3 4 5 6 7 8 9 10
10

last=3:変わらない


i=5

1 2 3 4 5 6 7 8 9 10
10

last=4:"3"と"7"の交換


i=6

1 2 3 4 5 6 7 8 9 10
10

last=4:変わらない


i=7

1 2 3 4 5 6 7 8 9 10
10

last=4:変わらない


i=8

1 2 3 4 5 6 7 8 9 10
10

last=4:変わらない


i=9

1 2 3 4 5 6 7 8 9 10
10

last=5:"4"と"7"の交換


i=10

1 2 3 4 5 6 7 8 9 10
10

last=6:"1"と"9"の交換


4.最後に1とlastの交換("6"と"1"の交換)して操作の終わり。

1 2 3 4 5 6 7 8 9 10
10
例プログラム

 このアルゴリズム使った例のプログラムQ-sort.tbtがここにあります。 以下はその実行結果です(多少変更しています)。ここでは 100個の文字列をクイックソートで整列しています。

クイックソートの計算量

 クイックソートの計算量はデータの並び方によって違います。データがランダムに並んでいたとすると,

比較回数は大体 2NlogNで,交換回数はその半分程度です。選択整列法に比べて比較回数が少ないことが目立ちます。大きなデータ数の場合この違いは歴然です。

 実際,私の手元のTiny Basic での実験によれば,5000件のデータでも数秒で,整列可能です。また上の例プログラムQ-sort.tbt でも速すぎて,動きを確認できないので,わざと遅延させています。