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

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

1 アルゴリズムとデータ構造 補足資料7-3 「単純選択ソートselsort.c」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

2 65 90 85 70 86 92 63 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 65 90 85 70 86 92 63 85 未整列

3 65 90 85 70 86 92 63 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 65 90 85 70 86 92 63 85 未整列 未整列エリアの最小

4 90 85 70 86 92 85 65 63 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 90 85 70 86 92 85 65 63 未整列 入れ替え 未整列エリアの最小

5 63 90 85 70 86 92 65 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 90 85 70 86 92 65 85 整列済み 未整列 入れ替え

6 63 90 85 70 86 92 65 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 90 85 70 86 92 65 85 整列済み 未整列

7 63 90 85 70 86 92 65 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 90 85 70 86 92 65 85 整列済み 未整列 未整列エリアの最小

8 63 90 85 70 86 92 65 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 90 85 70 86 92 65 85 整列済み 未整列 未整列エリアの最小 入れ替え

9 63 65 85 70 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 85 70 86 92 90 85 整列済み 未整列 未整列エリアの最小 入れ替え

10 63 65 85 70 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 85 70 86 92 90 85 整列済み 未整列 未整列エリアの最小

11 63 65 85 70 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 85 70 86 92 90 85 整列済み 未整列 未整列エリアの最小 入れ替え

12 63 65 70 85 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 86 92 90 85 整列済み 未整列 未整列エリアの最小 入れ替え

13 63 65 70 85 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 86 92 90 85 整列済み 未整列 未整列エリアの最小

14 63 65 70 85 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 86 92 90 85 整列済み 未整列 未整列エリアの最小

15 63 65 70 85 86 92 90 85 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 86 92 90 85 整列済み 未整列 未整列エリアの最小 入れ替え

16 63 65 70 85 85 92 90 86 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 92 90 86 整列済み 未整列 未整列エリアの最小 入れ替え

17 63 65 70 85 85 92 90 86 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 92 90 86 整列済み 未整列 未整列エリアの最小

18 63 65 70 85 85 92 90 86 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 92 90 86 整列済み 未整列 未整列エリアの最小 入れ替え

19 63 65 70 85 85 86 90 92 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 86 90 92 整列済み 未整列 未整列エリアの最小 入れ替え

20 63 65 70 85 85 86 90 92 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 86 90 92 整列済み 未整列 未整列エリアの最小

21 63 65 70 85 85 86 90 92 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 8件のデータ 63 65 70 85 85 86 90 92 整列済み

22 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの最小（最大）要素１個を探す 　　　　　　　→ あったら、候補と入れ替える n件のデータ 整列済 未整列 整列済 未整列

23 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す n件のデータ 整列済 未整列 整列済 未整列 i番目の要素 i番目の要素を整列済みにするためのコスト 入れ替え対象の場所を決めるのに：1～n-i回の比較 入れ替え対象の値を保持するのに：1～1+1/2+1/3+…+1/n回のデータ移動 繰り返し回数： n-1回

24 O(n2)の比較 整列済みのエリアと未整列のエリアに分けて考える。
解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す O(n2)の比較 データ移動回数については、参考書（N.ヴィルト著「アルゴリズムとデータ構造」）参照 n件のデータ 整列済 未整列 整列済 未整列 … n-1回の繰返し 整列済 未整列 それぞれ、およそ(n-i)/2回程度の比較 … 整列済 未整列 … 整列済 未整列 … 整列済 未整列 整列済 未整列