平成17年秋期  問12

コーヒーたろうさん  
(No.1)
こんにちは.
初めて質問させていただきます.

=====以下問題=====
キー値が等しい要素同士について,整列前の要素の順序(前後関係)を保つアルゴリズムを,安定な整列アルゴリズムという。次の二つの整列アルゴリズムに対して,安定にできるかどうかを考える。正しい組合せはどれか。

〔アルゴリズムとその特徴〕
・選択ソート
未整列の並びに対して,最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を,未整列の並びの長さを一つずつ減らしながら繰り返す。
・挿入ソート
未整列要素の並びの先頭の要素を取り出し,その要素を整列済みの要素の中の正しい位置に挿入する。
=====以下問題=====

この時解答は,選択ソート→「安定にできない」,挿入ソート→「安定にできる」となっています.
選択ソートとでは最小のキー値の見つけ方によっては(一番左から見つけることにする等)安定にできると考えているのですが,僕の考えはどこが間違っているのでしょうか.
2022.05.28 18:02
nsさん 
AP ブロンズマイスター
(No.2)
逆に言えば最小値の検索を適切に行わなければ安定でなくなる、ということなので、問題文の範囲内で考えれば「安定でない」という答えになるのでしょう。
2022.05.28 18:13
コーヒーたろうさん  
(No.3)
ご返信ありがとうございます!
なるほど...安定にできるかと言うのは,特に工夫を凝らさずに安定になるかと,言うことなんですかね
2022.05.28 19:25
コーヒーたろうさん  
(No.4)
ちょっと慣れてない部分もあるので,とりあえず引き続き解き進めたいと思います!
ありがとうございました!
2022.05.28 19:26
boyonboyonさん 
AP シルバーマイスター
(No.5)
例えば、未整列の並びとして
3,4,5,3,1,2
で考えます。
>最小のキー値をもつ要素と先頭の要素とを入れ換える
ので、先頭の3と1が入れ替わります。
1,4,5,3,3,2になります。
この結果、最初に先頭にあった3と4番目にあった3の順序が入れ替わります。
2022.05.28 20:54
nsさん 
AP ブロンズマイスター
(No.6)
boyonboyonさん
ありがとうございます。
最小値と入れ替えられる側のことがすっかり抜け落ちていました・・・

コーヒーたろうさん
No5のboyonboyonさんの回答が正しい考え方です。
No2の私のボケた回答は忘れてください。
2022.05.29 00:25

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop