課題12　「クイックソート」

内容

　　クイックソートを実装しなさい。

　　※ 最大で20個のデータがソートできればよい。（入力データ数は固定してもよい）

　　※ 入力されるデータは正の整数として仮定してもよい。

入力

　　20個の整数値

出力

　　クイックソートの実行結果（ソートされた20個の整数値）

実行

　　今回は特に値を指定しない。
　　20個の整数値を適当に入力し、実行せよ。

　　※ 大きな値を入れる必要は無いので、入力値 n は、-1000 ＜ n ＜ 1000 程度にすること。

　　※ ソートが正しく行われているかを確認するので、昇順や降順で値を入力することは避けること。

ヒント

出力例

　　入力を赤字で示した。（課題では20個の入力を行うこと）



　　input data
　　-10
　　5
　　-5
　　10
　　-15
　　15
　　5
　　sort data
　　-15 -10 -5 5 5 10 15　

クイックソート

　　クイックソートは、内部整列法(データをすべてメモリーに読み込んで行うソート)の中で最も高速であるとされている。
　　クイックソートもヒープソートと同様に、値を配列に格納する。



　　const
	N = 20;

　　var
　　　　A : array[1..N] of integer;　


　　今回も、20個のデータがソートできればいいので、N の値は20で良い。

　　クイックソートは、軸要素(pivot)と呼ばれる何らかのしきい値 a を設定し、

　	・グループS：a より小さい値のデータ集合
	・グループL：a 以上の値のデータ集合

　　といった2つのグループに分ける操作を繰り返して行うソートである。
　　(2回目以降はグループSとグループLに対して同様の操作を行う。)

　　図1は配列A={5,3,1,6,4,2}に対してクイックソートを実行した時の流れである。

　　


　　クイックソートを実装するに当たり、考えなければいけないのは以下の2つである。

	① 軸要素 a の選択方法
	② グループの分割方法

軸要素 a の選び方

　　軸要素はグループSとグループLが同じくらいのサイズになるように選ぶことが望ましい。
　　とは言え、軸要素の選択に時間をとっていては意味が無いので、それらしい数値を選択する方法として
　　大体以下の3つから選ばれる。

	(a) ランダムに1つ選ぶ.
	(b) ランダムに3つ選んで中央値を選ぶ.
	(c) 左からみて最初に得られた2つの異なる要素のうち大きい方を選ぶ.

　　本演習ではランダム生成について未学習なので、教科書でも用いられている(c)で実装を目指すことを勧める。
　　
　　※ 教科書P.84に、あるグループ(A[i],A[i+1],...,A[j])から軸要素を選択するプログラム PIVOT が記載されている。
　　　 PIVOT は軸要素そのものではなく、軸要素が格納されている配列番号を出力する関数であることに注意する。

グループの分割

　　ここでは、あるグループ(A[i],A[i+1],...,A[j])を、軸要素 a よりも小さいグループS(A[i],A[i+1],...,A[k-1])と、
　　軸要素 a 以上のグループL(A[k],A[k+1],...,A[j])に分割する方法について説明する。

	　A[i] , A[i+1] , A[i+2] , ... , A[j-2] , A[j-1] , A[j]
	→A[i] , A[i+1] , ... , A[k-1] , A[k] , A[k+1] , ... , A[j]

　　アルゴリズムは、大体以下のようになっている。

	1. 前述した関数PIVOTなどを用いて, 軸要素 a を選択する.
	2. 初期化として, 変数 l にグループの左端の配列番号である i , 
	　 変数 r にグループの右端の配列番号である j を代入する. 
	3. グループの要素を左側から調べ, a 以上の要素を探索する. 
	　 つまり, A[l]の要素と a を比較し,  A[l] ≧ a になるまで l を増加させる. 
	4. グループの要素を右側から調べ, a より小さい要素を探索する. 
	　 つまり, A[r]の要素と a を比較し,  A[r] ＜ a になるまで r を減少させる. 
	5. l ≦ r ならば, A[l]とA[r]を入れ替える.
	6. 3.の探索開始場所を l+1 , 3.の探索開始場所を r-1 にして
	　 3.から5.の手順を l ＞ r となるまで繰り返す. 
	7. 変数 k に l を代入する. k はグループSとグループLの境目を表す値であり, 
	　 次にグループSとグループLを分割する時に使用する. 

　　以下に図1で示した配列Aに対して、このアルゴリズムを実行した時の例を示す。
　　(ただし、初期状態から2段目の状態になるまでに限る)


	入力データ
		A = 5 , 3 , 1 , 6 , 4 , 2

	1. 軸要素の選択
		・左側から異なる2つの値を取り出す
			A = 5 , 3 , 1 , 6 , 4 , 2
		・値の大きい方を軸要素とする
			a = 5
	2. 初期化
		l := 1 , r := 6

	3. 左側から探索
		A = 5 , 3 , 1 , 6 , 4 , 2	{A[l] = 5 ≧ a (True)}

	4. 右側から探索
		A = 5 , 3 , 1 , 6 , 4 , 2	{A[r] = 2 ＜ a (True)}

	5. 入れ替え
		l = 1 , r = 6	{l ≦ r (True)}
		A = 2 , 3 , 1 , 6 , 4 , 5 

	6. 繰り返し
		実行する.	{l ＞ r (False)}

	3-2. 左側(続き)から探索
		l := l+1
		A = 2 , 3 , 1 , 6 , 4 , 5	{A[l] = 3 ≧ a (False)}
		l := l+1
		A = 2 , 3 , 1 , 6 , 4 , 5	{A[l] = 1 ≧ a (False)}
		l := l+1
		A = 2 , 3 , 1 , 6 , 4 , 5	{A[l] = 6 ≧ a (True)}

	4-2. 右側(続き)から探索
		r := r+1
		A = 2 , 3 , 1 , 6 , 4 , 5	{A[r] = 4 ＜ a (True)}

	5-2. 入れ替え
		l = 4 , r = 5	{l ≦ r (True)}
		A = 2 , 3 , 1 , 4 , 6 , 5

	6-2. 繰り返し
		実行する.	{l ＞ r (False)}

	3-3. 左側(続き)から探索
		l := l+1
		A = 2 , 3 , 1 , 4 , 6 , 5	{A[l] = 6 ≧ a (True)}

	4-3. 右側(続き)から探索
		r := r+1
		A = 2 , 3 , 1 , 4 , 6 , 5	{A[r] = 4 ＜ a (True)}

	5-3. 入れ替え
		l = 5 , r = 4	{l ≦ r (False)}

	6-3. 繰り返し
		実行しない.	{l ＞ r (True)}

	7. グループSとグループLの境目の保存
		k := l (= 5)

	分割結果
		A = 2 , 3 , 1 , 4 , 6 , 5


　　クイックソートは、分割されたグループSとグループLに対して更にグループの分割作業を行っていくことで、
　　徐々にデータをソートしていくことによって完遂する。