アルゴリズムとデータ構造 補足資料 7-3 「単純選択ソート selsort.c 」

アルゴリズムとデータ構造 補足資料 7-3

「単純選択ソート selsort.c 」

横浜国立大学

理工学部

数物・電子情報系学科

富井尚志

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

65 90 85 70 86 92 63 85

未整列

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 63 85

未整列

未整列エリアの最小

65

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 85

未整列

未整列エリアの最小 入れ替え

65 63

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 85

未整列 入れ替え

65 63

整列済み

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 85

未整列

65 63

整列済み

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 85

未整列

65 63

整列済み

未整列エリアの最小

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

90 85 70 86 92 85

未整列

65 63

整列済み

未整列エリアの最小

入れ替 え

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

85 70 86 92 85

未整列

63

整列済み

未整列エリアの最小 入れ替 え

90

65

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

85 70 86 92 85

未整列

63

整列済み

未整列エリアの最小

90

65

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

85 70 86 92 85

未整列

63

整列済み

未整列エリアの最小

90 65

入れ替 え

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

86 92 85

未整列

63

整列済み

未整列エリアの最小

90 65

入れ替 え

85

70

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

86 92 85

未整列

63

整列済み

未整列エリアの最小

90

65 70 85

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

86 92 85

未整列

63

整列済み

未整列エリアの最小

90

65 70 85

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

86 92 85

未整列

63

整列済み

未整列エリアの最小

90 65 70 85

入れ替 え

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

92

未整列

63

整列済み

未整列エリアの最小

90 65 70 85

入れ替 え

85 86

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

92

未整列

63

整列済み

未整列エリアの最小

90

65 70 85 85 86

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

92

未整列

63

整列済み

未整列エリアの最小

90

65 70 85 85 86

入れ替 え

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

未整列

63

整列済み

未整列エリアの最小

90 65 70 85 85

入れ替 え

86 92

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

未整列

63

整列済み

未整列エリアの最小

90

65 70 85 85 86 92

解の方針：未整列のエリアの最小（最大）要素１個を探す

8

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

63

整列済み

90

65 70 85 85 86 92

未整列

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

整列済

解の方針：未整列のエリアの最小（最大）要素１個を探す

→ あったら、候補と入れ替える

未整列

整列済

解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す 整列済みのエリアと未整列のエリアに分けて考える。

i

番目の要素 入れ替え対象の場所を決めるのに：

～

回の比較

入れ替え対象の値を保持するのに：

～

回のデータ移動

番目の要素を整列済みにするためのコスト

繰り返し回数：

回

未整列

件のデータ

整列済

未整列

整列済

解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す

n

件のデータ

整列済みのエリアと未整列のエリアに分けて考える。

整

未整列

列 済

未整列

整列済

未整列 整列済

未整列 整列済

未整列 整列済

整列済

未 整列

整列済

…………

n-1

回の繰返し

それぞれ、およそ

回程度の比較

O(n

) ^の比較

データ移動回数については、参考書（N.ヴィルト著「アルゴリズムとデータ構造」）参照