アルゴリズムとデータ構造 補足資料7-4 「単純交換ソートexsort.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 85 90 70 86 92 63 85 比較 ＞！ 入替！ 未整列 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 90 70 86 92 63 85 比較 未整列 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 90 86 92 63 85 比較 未整列 ＞！ 入替！ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 90 86 92 63 85 比較 未整列 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 92 63 85 比較 未整列 ＞！ 入替！ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 92 63 85 未整列 比較 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 92 63 85 未整列 比較 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 92 85 未整列 比較 ＞！ 入替！ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 92 85 未整列 比較 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 85 92 未整列 比較 ＞！ 入替！ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 85 92 未整列 整列済み 未整列エリアの 最大要素！ 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 85 92 未整列 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 85 70 86 90 63 85 92 未整列 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 70 85 86 63 85 90 92 未整列 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 70 85 86 63 85 90 92 未整列 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 65 70 85 63 85 86 90 92 未整列 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている 8件のデータ 63 65 70 85 85 86 90 92 整列済み 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている n件のデータ 未整列 未整列 整列済 整列済 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている n件のデータ 未整列 未整列 整列済 整列済 i個の要素から、隣同士の入れ替えで最大値を追い出すためのコスト 入れ替え対象の場所を決めるのに：i-1回の比較 入れ替え対象の値を保持するのに：0～i-1回のデータ移動 繰り返し回数： n-1回 整列済みのエリアと未整列のエリアに分けて考える。 解の方針：未整列のエリアで隣同士を比較・入れ替えながら整列済みエリアをつくる →入れ替えると、未整列エリアの最大（最小）要素が追い出される →泡が立ち上っていく様子に似ている の比較 O(n2) n件のデータ 整 列 済 未整列 未整列 整列済 … n-1回の繰返し 未整列 整列済 … それぞれ、およそ(n-i)/2回程度の比較 未整列 整列済 … 未整列 整列済 … 未整列 未 整 列 整列済 整列済
© Copyright 2024 ExpyDoc
