ホーム » 「クイックソート」タグがついた投稿
タグアーカイブ: クイックソート
再帰呼び出しと再帰方程式
前回の授業では、簡単な再帰呼び出しのプログラムについて再帰方程式などの説明を行った。今日の授業では、ハノイの塔の処理時間や、マージソートのプログラムの処理時間について検討を行う。
ハノイの塔
ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。
… ①
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、
枚では、
… ③より
… ①を代入
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
理解度確認
- 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
- 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
int a[ 10 ] = {
7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
// 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
if ( __________ ) {
return ____ ; // 見つからなかった
} else {
int M = _________ ;
if ( array[ M ] == key )
return ____ ;
else if ( array[ M ] > key )
return find( array , ___ , ___ , key ) ;
else
return find( _____ , ___ , ___ , ___ ) ;
}
}
int main() {
if ( find( a , 0 , 10 , 56 ) )
printf( "みつけた¥n" ) ;
}
再帰を使ったソートアルゴリズムの分析
データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。
この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
- 参考: マージソート(併合整列法)
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。
：
よって、処理時間のオーダはとなる。
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓などが必要。[解説]
ソート処理の見積もりとポインタ処理
前回の授業では、再帰処理やソートアルゴリズムの処理時間の見積もりについて説明を行った。
ソート処理の見積もり
この際の練習問題の1つめは、「再帰方程式の理解度確認の回答」にて解説を示す。
最後の練習問題はここで説明を行う。
選択法とクイックソートの処理時間の比較
例として、データ数N=20件で、選択法なら10msec、クイックソートで20msecかかったとする。
これより、選択法の処理時間を、クイックソートの処理時間を
、とすると、
よって、
処理時間が逆転するときのデータ件数は、2つのグラフの交点を求めることになるので、
より、以下の式を解いた答えとなる。これは通常の方程式では解けないが電卓で求めると、N=53.1 ほどかな。(2020/05/26) 真面目に解いたら N=53.017 だった。
実際にも、クイックソートを再帰呼び出しだけでプログラムを書くと、データ件数が少ない場合は選択法などのアルゴリズムの方が処理時間が早い。このため、C言語などの組み込み関数の qsort() などは、データ件数が20とか30とか一定数を下回ったら、再帰を行わずに選択法でソートを行うのが一般的である。
ポインタ処理
ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。
値渡し(call by value)
// 値渡しのプログラム
void foo( int x ) { // x は局所変数(仮引数は呼出時に
// 対応する実引数で初期化される。
x++ ;
printf( "%d¥n" , x ) ;
}
void main() {
int a = 123 ;
foo( a ) ; // 124
// 処理後も main::a は 123 のまま。
foo( a ) ; // 124
}
このプログラムでは、aの値は変化せずに、124,124 が表示される。
言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？
// 大域変数を使う場合
int x ;
void foo() {
x++ ;
printf( "%d¥n" , x ) ;
}
void main() {
x = 123 ;
foo() ; // 124
foo() ; // 125
}
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
for( i = 0 ; i < 2 ; i++ )
printf( "A" ) ;
}
void main() {
for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と
foo() ; // 表示されない。
}
ポインタ渡し(call by pointer)
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。
// ポインタ渡しのプログラム
void foo( int* p ) { // p はポインタ
(*p)++ ;
printf( "%d¥n" , *p ) ;
}
void main() {
int a = 123 ;
foo( &a ) ; // 124
// 処理後 main::a は 124 に増えている。
foo( &a ) ; // 124
} // さらに125と増える。
C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は：結果を入れてもらう場所を伝え、関数側は：指定されたアドレスに結果を書む。
ポインタの加算と配列アドレス
ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。
// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;
void main() {
int* p ;
// p∇
p = &a[2] ; // a[] : 11,22,33,44,55
// -2 +0 +1
printf( "%d¥n" , *p ) ; // 33 p[0]
printf( "%d¥n" , *(p+1) ) ; // 44 p[1]
printf( "%d¥n" , *(p-2) ) ; // 11 p[-2]
p = a ; // p∇
printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55
p++ ; // → p∇
printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55
p += 2 ; // → → p∇
printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55
}
ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。
*(p + 整数式) と p[ 整数式 ] は同じ意味
特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
struct Person {
char name[ 10 ] ;
int age ;
} ;
struct Person table[3] = {
{ "t-saitoh" , 55 } ,
{ "tomoko" , 44 } ,
{ "mitsuki" , 19 } ,
} ;
void print_Person( struct Person* p ) {
printf( "%s %d\n" ,
(*p).name , // * と . では . の方が優先順位が高い
// p->name と簡単に書ける。
p->age ) ; // (*p).age の簡単な書き方
}
void main() {
for( int i = 0 ; i < 3 ; i++ ) {
print_Person( &(table[i]) ) ;
// print_Person( table + i ) ; でも良い
}
}
構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。
練習問題(2018年度中間試験問題より)
ソートアルゴリズム
前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。
様々なソートアルゴリズム
データの有名な並び替えアルゴリズムとその処理時間のオーダーを示す。
- バブルソート O(N2)
- 選択法 O(N2/2)
- クイックソート O( N log N )
- マージソート O( N log N )
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。
：
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。