アルゴリズムとデータ構造 補足資料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件のデータ 63 65 70 85 86 90 92 85 整列済み 未整列 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す 8件のデータ 63 65 70 85 86 90 92 85 整列済み 未整列 これは、整列済エリアのどこに入る？ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す 8件のデータ 63 65 70 85 整列済み 86 90 92 85 未整列 これは、整列済エリアのどこに入る？ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す 8件のデータ 63 65 70 85 85 86 90 92 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す n件のデータ 整列済 未整列 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す n件のデータ 整列済 未整列 i番目の要素 i番目の要素を整列済みにするためのコスト 挿入先を決めるのに：1～i回の比較 挿入先を空けるのに：0～i-1回のデータ移動 繰り返し回数： n-1回 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアの要素１個を、整列済みのエリアのどこに「挿入」すればよいか探す O(n2) n件のデータ 整 列 済 未整列 未整列 整列済 … 整列済 n-1回の繰返し 未整列 … それぞれ、およそi/2回程度の比較とデータ移動 整列済 未整列 … 整列済 未整列 … 整列済 整列済 未整列 未 整 列
© Copyright 2024 ExpyDoc
