平成17年秋期試験問題 午前問12
問12解説へ
キー値が等しい要素同士について，整列前の要素の順序(前後関係)を保つアルゴリズムを，安定な整列アルゴリズムという。次の二つの整列アルゴリズムに対して，安定にできるかどうかを考える。正しい組合せはどれか。
〔アルゴリズムとその特徴〕
〔アルゴリズムとその特徴〕
- 選択ソート
- 未整列の並びに対して，最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を，未整列の並びの長さを一つずつ減らしながら繰り返す。
- 挿入ソート
- 未整列要素の並びの先頭の要素を取り出し，その要素を整列済みの要素の中の正しい位置に挿入する。
広告
解説
〔選択ソートについて〕
キー値が同じ要素があった場合には、どちらが先に先頭要素との入替えが行われるかによって整列後の前後関係が変わってきます。したがって「安定にできない」が適切です。
〔挿入ソートについて〕
未整列要素の先頭から順に整列済みの要素の位置に挿入されていくため、既に整列済みの要素中に同じキー値の要素が存在している場合、常にその要素の後ろに挿入することで整列前の前後関係を保つことが可能です。したがって「安定にできる」が適切です。
よって正しい組合せは「ウ」になります。
キー値が同じ要素があった場合には、どちらが先に先頭要素との入替えが行われるかによって整列後の前後関係が変わってきます。したがって「安定にできない」が適切です。
〔挿入ソートについて〕
未整列要素の先頭から順に整列済みの要素の位置に挿入されていくため、既に整列済みの要素中に同じキー値の要素が存在している場合、常にその要素の後ろに挿入することで整列前の前後関係を保つことが可能です。したがって「安定にできる」が適切です。
よって正しい組合せは「ウ」になります。