Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Similar presentations


Ads by Google