クイックソート
クイックソートアルゴリズムの仕組み、分割統治法の考え方
、計算量の評価方法
【学習内容の構成】
1. 計算量の基礎：アルゴリズムの性能を評価する指標とし
ての時間計算量とO記法
2. クイックソートの手順：pivotの選択、要素の分割、再帰
的なソートの適用
3. 分割統治法：問題を部分問題に分割し再帰的に解く手
法
4. 計算量の分析：平均O(n log n)、最悪O(n²)となる条件と
基準値選択の工夫
• 前提：プログラミングの基礎、再帰の概念、線形探索の
理解
• 意義：効率的なソートアルゴリズムの設計原理の習得、
実装と性能評価の実践
計算量とは
• アルゴリズムのよしあしを評価する基準
– 領域計算量(space complexity)
• 計算機のメモリーをどれだけ必要とするか
– 時間計算量(time complexity)
• アルゴリズムが答を出すまでにどの程度の計算時
間を必要とするか
• プログラム中のそれぞれの文が実行される回数を
数えて計算量の目安をつける
計算量の評価
47 12 33
・・・
5 67
table[]
1:
2:
3:
4:
5:
found = false;
for ( i=0 ; i<n ; i++ ){
if ( x == table[i] ){
found = true;
break;
}
}
ループを回る回数がk回のとき、つまり
x=table[k-1]のときの計算時間（概算）は
T(k)=t
1
+k(t
2
+t
3
)+t
4
+t
5
ループを回る回数の平均は約
n/2
回
最悪の場合
(k=n)
の計算時間は
T= t
1
+t
4
+t
5
+n(t
2
+t
3
)
n
が大きくなれば定数
t
1
+t
4
+t
5
は無視でき、
T
はおよそ
n
に比例する
T=cn (c=t
2
+t
3
)
線形探索アルゴリズム
O記法ではO(n)とあらわす
クイックソートの手順
1. pivot の選択
• ソートする範囲の中から pivot を1つ選ぶ
2. pivot による要素の分割
– pivot を使い「より大きい要素」と「より小さい要素」に
分割
– 要素を1つずつ調べて、基準値より小さい要素と，よ
り大きい要素を分ける
3. 分割された２つの部分に，再びクイックソートを
適用
– 「基準値より大きい要素」と「基準値より小さい要素」
のそれぞれを独立にソート
– 最後に、２つの部分と pivot をつなげる．全体がソー
トできたことになる
pivot の選択
８ １０ ６ ３ ５
リスト
８
pivot
ソートする範囲の中から pivot を選ぶ
（ここでは，リストの先頭要素を pivot として
選んでいる）
pivot による要素の分割
８ １０ ６ ３ ５
リスト
８
pivot
分割されたリスト
１０
６ ３ ５
要素を1つずつ調べて、基準値より
小さい要素と，より大きい要素を分ける
８ １０ ６ ３ ５
リスト
８
pivot
１０
６ ３ ５
リストが空になるまで，pivot の選択と，
pivot による要素の分割を続ける
１０
pivot
リスト
６
３ ５
３
部分問題の例
• 休暇旅行の旅程（家から旅先のホテルま
で）
– 家→空港
– 空港→旅先の空港
– 旅先の空港→ホテル
クイックソートの部分問題
1. 「基準値より大きい要素」のソート
2. 「基準値より小さい要素」のソート
分割統治法(divide and conquer)
• サイズNの問題を解くのに、サイズが
約N/2の部分問題2つに分けて、それ
ぞれを再帰的に解き、その後でその2
つの解を合わせて目的の解を得る
クイックソート
• 分割統治法に分類されるソート法
• 平均して O(nlog n) の計算量でソートを行なうア
ルゴリズム
– ヒープソートの計算量も O(nlog n) だが、ヒープソート
に比べて基本操作が簡単なので、実際の計算量はク
イックソートの方が有利と言われる
– 多くの問題に対して、最高速のソートアルゴリズムで
あると言われているそうですが、
• 最悪の場合には，O(n
2
) の計算量を要することが
知られている
クイックソートの手順
• ソートする範囲の中から適当な値を1つ選ぶ
– この値を基準値と呼ぶ
• 次に配列中の要素を1つずつ調べて、基準値より
小さいデータを配列の左側、大きなデータを右側
に集める
– この操作を分割と呼ぶ
• 分割が終わったら、基準値より小さい部分と大き
い部分に，それぞれに再びクイックソートを適用
– これは再帰呼び出しで実現
• 分割された2つの部分を独立にソートすれば全体
もソートされたことになる
– 基準値より小さい部分に含まれる値は基準値より大
きい部分に含まれるどの値よりも小さいから
基本的な分割法
• ソートすべき範囲を left～right とする
• まず基準値Tを選び、この値を left に移し
ておく
– left の値は今まで基準値があった場所に移す
• 次に、left+1～right の範囲を分割する
ある時点 i まで分割が終わった状態
left+1～m の範囲に T 未満の値、
m+1～i までの範囲に T 以上の値が残る
m m+1 i
T < T >= T
？
• i を１増やした後の i 番目の要素は，次の２通り
1) i 番目の値が T以上：
何もしない
2) i 番目の値が T より小さい
m を 1 増やし、小さい要素のための新たな場所を指すよう
にして、次にそこにある要素と i 番目の要素を交換する
• これを i が right にいたるまで繰り返す
m
i
T < T >= T
？
m i
T < T >= T
？
<T
交換
クイックソートの平均計算量
• ソートする範囲の要素数をnとする
• 1回の分割での比較の回数： n-1
• 長さnのクイックソートに要する計算量：
Q
n
= n-1+ Q
a
+Q
b
– ここで a, b は分割によって生じた左右の部分
の長さ
– a+b = n-1 が成立
– a と b の組は分割の回数によって決まる
– 平均をとると，Q
n
= n-1+ 2/n(Q
0
+…+Q
n-1
)
– これを計算すると
Q
n
= 2(n+1)( 1+1/2+…+1/(n+1) - 2 ) +2
Q
n
≒ 2nlog n
n=4のときの計算量
pivot
Q
2
=1
Q
1
=0
Q
3
=2+ 2Q
2
/3
Q
4
= 3+(2Q
3
+2Q
2
)/4
最悪の場合
• 最悪の場合とは、分割した結果、一方の組に n-1
個の要素が残り、もう一方の組が空になる場合
• 基準値として最大または最小の値をとった場合
に起こる
• 分割を行うたびにこのような状態になったとする
と、比較の回数は
Q
n
=(n-1)+(n-2)+…+1 = (n(n-1))/2
基準値の選び方
• 「最悪の場合」から分かるように、基準値の選び方
が，性能の鍵
• 最悪の計算量になる場合とは逆に，分割させる範
囲をなるべく同じ長さの２つの部分に分けるような値
を選ぶ
• しかし、分割のたびに中央値を求めるのでは、その
ための手間がかかりすぎる
• 実用的な方法は，ソートする範囲の中からいくつか
の値をサンプルとして選び、それらの中央値を基準
とする方法です。
– サンプルとしてとる値の個数は多いほど分割を均等化す
るためにはよい
– 実際には３個とれば十分だとされている
簡単なソート法の併用
• ソートすべき範囲が短い場合には、クイック
ソートよりも単純な方法(挿入法など)と差が
無い
• 高級なアルゴリズムは、単純な方法より計算
量のオーダーが低い
– 対象とするデータが多い場合には明らかに速い
– データが少ない場合にはオーダーの問題とはな
らないことがありえる
– １０～２０の範囲内であれば，どれを選んでも大
差はないといわれている
例題 クイックソート
• 次の２つのクイックソートプログラムを作成し，性
能を比較する（平均の比較回数は6 / 7程度に減
り、実際の実行時間は5%ほど減ると言われてい
る）
– 基準値を適当な値にとるプログラム
– ソートする範囲から３つのサンプルを選び，その中央
値を基準値として使うプログラム
• ソート対象のデータは rand関数等を用いて生成
すること
#include<stdio.h>
FILE *infile,*outfile;
int data[10000];
main()
{
int i, n, in[20], out[20];
printf("Input InFilename :"); /*入力データのファイル名を入力*/
scanf("%s", in);
if ((infile=fopen(in,"r"))==NULL) {
printf("can't open file %s¥n", in);
exit();
}
printf("Input OutFilename :");
scanf("%s", out);
if ((outfile=fopen(out,"w"))==NULL) {
printf("can't open file %s¥n",out);
exit();
}
n=0;
while(fscanf(infile, "%d", &(data[n])) != EOF) {
n++;
}
Quick(0,n-1); /*0からn-1の範囲でクイックソート*/
for (i=0; i<n; i++) {
fprintf(outfile,"%d¥n",data[i]);
}
fclose(outfile);
fclose(infile);
}
Quick(int left,int right)
{ /*クイックソートを行う*/
int i,t,m;
t=Choice(left, right); /*基準値を選ぶ*/
swap(&data[left], &data[t]);
m=left;
for (i=left; i<right; i++){
if (data[i+1]<data[left]) { /*基準値よりも小さい場合*/
swap(&data[i+1], &data[m+1]);
m++;
}
}
swap(&data[left], &data[m]); /*基準値をmに挿入*/
if (m-left>1) {
Quick(left, m-1);
}
if (right-m>1) {
Quick(m+1, right);
}
}
int Choice(int left,int right)
{
/*基準値を選ぶ*/
if ((right-left)<2) {
return(left); /*要素数が3つないとき*/
}
else { /*要素数が3つ以上のとき*/
if((data[left]<=data[left+1] & data[left+1]<=data[left+2])
| (data[left+2]<=data[left+1] & data[left+1]<=data[left+2])) {
return(left+1); /*中央値を返す*/
}
else if((data[left+1]<=data[left] & data[left]<=data[left+2])
| (data[left+2]<=data[left] & data[left]<=data[left+1])) {
return(left);
}
else {
return(left+2);
}
}
}
swap(int *a, int *b){
/*値の交換*/
int temp;
temp=*a;
*a=*b;
*b=temp;
}