ソートアルゴリズムの種類
• 選択ソート (selection sort)
• バブルソート (bubble sort) 前回の授業
• 挿入ソート (insertion sort) で説明
• クイックソート (quick sort)
• マージソート (merge sort)
今回の授業
で説明
クイックソート ― 基本的なアイディア
63 39 28 73 45 11 31 94
小さい数のグループ
31 39 28 11 45
数字 を大きい数と
小さい数の
２グループに分割
大きい数のグループ
73 63 94
左のグループの要素≦右のグループの要素
各々を再帰的にソート
11 28 31 39 45
63 73 94
クイックソート ― 分割方法（その１）
８つの数字の中からひとつ選ぶ
（ピボット）
63 39 28 73 45 11 31 94
一番左の値をピボットとする
左のグループの要素≦ピボット≦右のグループの要素
となるように分割
11 28 31 39 45
63 73 94
クイックソート ― 分割方法（その２）
左のグループの要素≦ピボット≦右のグループの要素 と分割したい
63
（１）左側からピボット
以上の値を探す
（２）右側からピボット
以下の値を探す
63 39 28 73 45 11 31 94
（３）２つの数字を交換
31 39 28 73 45 11 63 94
クイックソート ― 分割方法（その３）
（１）左側からピボット以上の
値を探す
（２）右側からピボット以下の
値を探す
31 39 28 73 45 11 63 94
（３）数字を交換
31 39 28 11 45 73 63 94
（１）ピボット以上の値を探す
（２）ピボット以下の値を探す
31 39 28 11 45 73 63 94
（４）●が●の左にきたら終了。
分割。
31 39 28 11 45
73 63 94
クイックソート ― 全体の流れ
63 39 28 73 45 11 31 94
31 39 28 11 45
11 28
11
28
73 63 94
39 31 45
31
63
39 45
39
73 94
73
94
45
39 45
11 28
31 39 45
11 28 31 39 45
73 94
63 73 94
マージソート ― 基本的なアイディア
63 39 28 73 45 11 31 94
配列を２分割
63 39 28 73 45 11 31 94
各々を再帰的に
ソート
28 39 63 73 11 31 45 94
２つの配列を
マージ
11 28 31 39 45 63 73 94
ソート完了
マージソート ― マージのやり方（その１）
ソートされている２つの配列をマージ
28 39 63 73 11 31 45 94
各配列の先頭の数字を比較
＝＞小さいほうが最小値
＝＞作業用の配列の先頭へ
11
作業用の配列
Bを用意
マージソート ― マージのやり方（その２）
28 39 63 73
31 45 94
各配列の先頭の数字を比較
＝＞小さい方を作業用の配列へ
11 28
39 63 73
11 28 31
31 45 94
マージソート ― マージのやり方（その３）
次々に作業用の配列に挿入
39 63 73
45 94
11 28 31 39 45 63 73 94
マージ完了！
マージソート ― 全体の流れ
63 39 28 73 45 11 31 94
63 39 28 73
63 39
63
39
39 63
28 73
28
73
28 73
28 39 63 73
分割
45 11 31 94
分割
45 11
31 94 分割
45
31
11
11 45
31 94
11 31 45 94
11 28 31 39 45 63 73 94
94
マージ
マージ
マージ

ソート回路のハードウェア化

選択ソート(selection sort)

PowerPoint プレゼンテーション