アルゴリズムとデータ構造 補足資料 7-4
「単純交換ソート exsort.c 」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 90 85 70 86 92 63 85
未整列
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 90 85 70 86 92 63 85
比較 未整列
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 90 85 70 86 92 63 85
比較 未整列
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 90 85 70 86 92 63 85
比較 未整列
＞！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 90 70 86 92 63 85
比較 未整列
＞！ 入替！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 90 70 86 92 63 85
比較 未整列
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 90 86 92 63 85
比較 未整列
＞！ 入替！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 90 86 92 63 85
比較 未整列
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 92 63 85
比較 未整列
＞！ 入替！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 92 63 85
未整列 比較
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 92 63 85
未整列 比較
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 92 85
未整列 比較
＞！ 入替！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 92 85
未整列 比較
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 85 92
未整列 比較
＞！ 入替！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 85 92
未整列 整列済み
未整列エリアの
最大要素！
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 85 92
未整列 整列済み
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 85 70 86 90 63 85 92
未整列 整列済み
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 70 85 86 63 85 90 92
未整列 整列済み
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 70 85 86 63 85 90 92
未整列 整列済み
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
8件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
65 70 85 63 85 86 90 92
未整列 整列済み
8
件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
63
整列済み
90
65 70 85 85 86 92
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
未整列
n
件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
整列済
未整列 整列済
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
未整列
n
件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
整列済
未整列 整列済
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
→泡が立ち上っていく様子に似ている
入れ替え対象の場所を決めるのに：
i-1回の比較
入れ替え対象の値を保持するのに：
0～
i-1回のデータ移動
i
個の要素から、隣同士の入れ替えで最大値を追い出すためのコスト
繰り返し回数：
n-1回
n
件のデータ
整列済みのエリアと未整列のエリアに分けて考える。
未整列
整列済未整列
整列済未整列 整列済
未整列 整列済
未整列 整列済
未整列
整列済
未
整列
整列済
…………
n-1
回の繰返し
それぞれ、およそ
(n-i)/2回程度の比較
O(n
2) の比較
解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる
→入れ替えると、未整列エリアの最大（最小）要素が追い出される
