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