アルゴリズムとプログラミング (Algorithms and Programming)

Presentation on theme: "アルゴリズムとプログラミング (Algorithms and Programming)"— Presentation transcript:

1 アルゴリズムとプログラミング (Algorithms and Programming)
第９回：クイックソート ソーティングアルゴリズム クイックソート 講義資料等：

2 ソーティングアルゴリズム 選択ソート マージソート クイックソート バブルソート ヒープソート

3 クイックソートの考え方 問題： 配列の要素を、小さい順に並べ替える 方針： １．基準となる大きさの要素(pivot)を選ぶ
　　グループ分けする （”未満”の要素は左詰、”以上”の要素は右詰） 3.分割された各グループに対して同じことを繰り返す ４．全てのグループの要素の数が１つになるまで繰り返す

4 1. pivot(基準となる軸)を選択 pivot選択の方法： 方法１．先頭または最後の要素を選ぶ 方法２．中央にある要素を選ぶ
　方法１．先頭または最後の要素を選ぶ 　方法２．中央にある要素を選ぶ 　方法３．適当に選んだ３つの要素のうち、中央の値をとる 　．．．etc

5 ２．pivot未満のグループと、 pivot以上のグループにグループ分けする

6 ３．分割されたそれぞれのグループに対して 同様の分割を繰り返す
未満 以上 未満 以上

7 すべてのグループの要素が１つになったとき、
ソート完了

8 pivot選択の方法 簡単な方法で、なるべく分割が均等になるとよいが、 pivotの選び方が複雑だと計算時間が増えてしまう。
従って、限りなく機械的に選ぶ方法が採用される。 （もちろん、裏目に出ることもある。。） 方法１．先頭または末尾の要素を選ぶ 方法２．中央にある要素を選ぶ 方法３．先頭、中央、末尾の３つの要素の中央の値をとる ．．．etc

9 最悪な分割 たとえば、 大きい順に並んでいる配列に対して 先頭要素（最大要素)をpivotとして 選択してしまった場合

10 pivotよりも 小さいグループ pivotと同じか 大きいグループ このままいくと、分割が完了するまでに N回の分割が必要になってしまう！

11 最善の分割 ちょうど半分づつ に分割していくと 分割回数が最少 分割回数は log2N

12 クイックソートの計算量 N・log2N N2 各分割では、値の比較と代入で オーダーとしてN回の演算操作が必要。
これに分割段数を乗ずれば全体の計算量 となる。 最善の分割に近い分割なら 計算量のオーダーとして N・log2N ただし、最悪ケースでは N2

13 クイックソートの例-1 （与えられた配列と同じサイズの作業用配列を用意できる場合） pivot 与えられた配列 4 7 3 5 8 2 6 1 pivot 一番左側の4をpivotとする 4 4 7 3 5 8 2 6 1 作業用 配列 4 4は4以上なので作業用配列に右詰で格納する

14 4 7 3 5 8 2 6 1 7 4 4 3 5 8 2 6 1 3 7 4 pivot 先頭から２番目の7をpivotと比べる 作業用
配列 7 4 7は4以上なので作業用配列に右詰で格納する pivot 先頭から３番目の3をpivotと比べる 4 3 5 8 2 6 1 作業用 配列 3 7 4 3は4より小さいので作業用配列に左詰で格納する

15 4 5 8 2 6 1 3 5 7 4 4 8 2 6 1 3 8 5 7 4 pivot 先頭から4番目の5をpivotと比べる 作業用
配列 3 5 7 4 5は4以上なので作業用配列に右詰で格納する pivot 先頭から5番目の8をpivotと比べる 4 8 2 6 1 作業用 配列 3 8 5 7 4 8は4以上なので、作業用配列に右詰で格納する

16 4 2 6 1 3 2 8 5 7 4 4 6 1 3 2 6 8 5 7 4 pivot 先頭から6番目の2をpivotと比べる 作業用
配列 3 2 8 5 7 4 2は4より小さいので作業用配列に左詰で格納する pivot 先頭から7番目の6をpivotと比べる 4 6 1 作業用 配列 3 2 6 8 5 7 4 6は4以上なので、作業用配列に右詰で格納する

17 4 1 3 2 1 6 8 5 7 4 3 2 1 6 8 5 7 4 pivot 先頭から8番目の1をpivotと比べる 作業用 配列
1は4より小さいので作業用配列に左詰で格納する 左詰した要素と右詰した要素のグループで２分割される 4未満のグループと4以上のグループに分割された pivot 3 2 1 6 8 5 7 4 それぞれのグループに対して同じことを行い、要素が１つ 　　　　　　　　　　　　　　　になるまで分割を繰り返す 作業用 配列

18 pivot 結果だけ記す 3 3 2 1 6 8 5 7 4 作業用 配列 3 2 3 2 1 3 pivot "3"は要素が１つに なったので分割完了 2 2 1 作業用 配列 2 1 2 分割完了⇒(この部分は)ソート完了

19 pivot 今度はこちらのグループ 6 1 2 3 6 8 5 7 4 作業用 配列 6 8 6 5 8 6 pivot 5 7 8 6 5 5 4 5 4 7 8 6 作業用 配列 5 4 5 残りは次ページ 完了

20 7 7 8 6 7 8 7 6 8 7 8 8 7 8 7 8 pivot 作業用 配列 pivot 作業用 配列 以上で全て要素が１つ
今度はこちらのグループ pivot 7 7 8 6 作業用 配列 7 8 7 6 8 7 pivot 8 8 7 作業用 配列 8 以上で全て要素が１つ だけになったので ソート完了 7 8

21 クイックソートの例-2 （要素１つ分の作業用領域を使用する場合） pivot 作業用領域 ●与えられた配列 4 7 3 5 8 2 6 1 pivot 作業用領域 ●先頭の４をpivotとする 4 4 7 3 5 8 2 6 1 ●並べ替えのため、先頭の４を作業領域へ pivot 作業用領域 4 4 7 3 5 8 2 6 1 ●4は4以上なので、1を作業領域へ移して 　 4を配列の最後に置く pivot 作業用領域 4 1 7 3 5 8 2 6 4

22 ●1は4より小さいので配列の先頭におき、その次の7を取り出す
pivot 作業用領域 4 7 1 3 5 8 2 6 4 ●7は4以上なので、配列の最後から２番目の6を取り出し、7を置く pivot 作業用領域 4 6 1 3 5 8 2 7 4 ●6は4以上なので、配列の最後から3番目の2を取り出し、6を置く pivot 作業用領域 4 2 1 3 5 8 6 7 4 ●2は4より小さいので、配列の先頭から2番目に置き、次の3を取る pivot 作業用領域 4 3 1 2 5 8 6 7 4

23 ●3は4より小さいので、配列の先頭から3番目に置き、次の5を取る
pivot 作業用領域 4 5 1 2 3 8 6 7 4 ●5は4以上なので、配列の最後から4番目の8を取り出し、5を置く pivot 作業用領域 4 8 1 2 3 5 6 7 4 ●8は4以上なので、配列の最後から5番目に8を置く pivot 作業用領域 4 1 2 3 8 5 6 7 4 以上より、前半が４未満、後半が4以上のグループに分割された。 同じことをそれぞれのグループに対して繰り返し適用する。 すべてのグループが要素１つになるまで分割を繰り返す。

24 まとめ ソーティング(並べ替え)アルゴリズム クイックソート
pivotを決めて、それ以上の要素と未満の要素にグループを分割していくアルゴリズム