アルゴリズムとデータ構造 補足資料 7-2 「単純挿入ソート insort.c 」

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

「単純挿入ソート insort.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 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 90 70 86 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 85 90

70 86 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 90 86 92 63 85

整列済み 未整列

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

8

件のデータ

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

65 70 85 90 86 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 90

86 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 86 90 92 63 85

整列済み 未整列

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

8

件のデータ

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

65 70 85 86 90 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 86 90 92 63 85

整列済み 未整列

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

8

件のデータ

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

65 70 85 86 90 92 63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 86 90 92

63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 86 90 92

63 85

整列済み 未整列

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

8

件のデータ

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

65 70 85 86 90 92

63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 90

85

70 86 92

63 85

整列済み 未整列

これは、整列済エリアのどこに入る？

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

8

件のデータ

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

65 70 85 86 90 92

63 85

整列済み

未整列

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

n

件のデータ

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

整列済

未整列

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

n

件のデータ

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

整列済

i

番目の要素

挿入先を決めるのに：

～

回の比較

挿入先を空けるのに：

～

回のデータ移動

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

繰り返し回数：

回

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

n

件のデータ

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

整

未整列

列 済

未整列

整列済

未整列 整列済

未整列 整列済

未整列 整列済

整列済

未 整列

整列済

…………

n-1

回の繰返し

それぞれ、およそ

回程度の比較とデータ移動

O(n

)