同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。
と書いてあるように、同じ値の順序性が維持されるかになります。
極端な例をあげれば、
を並べ替えようとしたとき、(値としてはいずれも1だが)元々 x[0] に入っていたものと、 x[1] に入っていたものとx[2]に入っていたものが同じ順序に並ぶかどうかで決まるという意味ですね。
数値だけだとわかりにくいですが、トランプで考えるとスペードのエースとクラブのエースとハートのエースを並び替えたとき(並び替えはカードの値のみ)、スペードのエースが常に先にくるなら、安定なソートと言えます。
たとえば、以下の2つの配列でバイナリソート(問題にないので)を考えます(コードは書きません)、
ただし、ソートはxに対して行い、xを入れ替えるとき markも同じように入れ替える事とします。
x = [1,1,1]
mark=["s","c","h"] # スペード、クラブ、ハート
中央値はクラブの1 ( index = 1 )です。
ソート手順1 左側から自分以上(同じ値を含む)を検索して右側の最後に移動します。
- スペードの1 (index = 0)は同じ数字なので右側の最後に移動されます。
xを入れ替えます。markも同じように入れ替えます。
ソート手順2 右側から自分より小さい(同じ値含まない)ものを検索して左側の最後に移動します。
- 右側にいるハートの1は自分と同じ値なので移動は起きません。
結果は以下になります。
x = [1,1,1]
mark=["c","h","s"] # クラブ、ハート、スペード
今回はもう並び替えの必要が無いことがわかるのでこれでおしまいです。
スペード、クラブ、ハートの並びがクラブ、ハート、スペードになってしまいました。
なので不安定です。
単純には元の順序を覚えておいて、並び替え後にそれを使って評価すればいいと思います。
工夫のしどころはありますが、それ書いたら問題の意義が失われるのでそれは自分で考えてください。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/09/02 03:18