安定なソート stable sortとは？

Question

Aizu Online Judgeで勉強しているのですが、安定なソートというのがよくわかりません。

何がわかっていないのかもわからないくらい、よくわかりません。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C&lang=jp

これは、どうすれば、アルゴリズムが書けて、どのようなアルゴリズムが、正解になるのでしょうか？

このアルゴリズムの考え方を教えて下さい。

よろしくお願い致します。

Answer 1

同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。

と書いてあるように、同じ値の順序性が維持されるかになります。

極端な例をあげれば、

x = [1,1,1]

を並べ替えようとしたとき、(値としてはいずれも1だが)元々 x[0] に入っていたものと、 x[1] に入っていたものとx[2]に入っていたものが同じ順序に並ぶかどうかで決まるという意味ですね。
数値だけだとわかりにくいですが、トランプで考えるとスペードのエースとクラブのエースとハートのエースを並び替えたとき(並び替えはカードの値のみ)、スペードのエースが常に先にくるなら、安定なソートと言えます。

たとえば、以下の2つの配列でバイナリソート(問題にないので)を考えます(コードは書きません)、
ただし、ソートはxに対して行い、xを入れ替えるとき markも同じように入れ替える事とします。

x = [1,1,1]
mark=["s","c","h"] # スペード、クラブ、ハート

中央値はクラブの1 ( index = 1 )です。
ソート手順１ 左側から自分以上(同じ値を含む)を検索して右側の最後に移動します。

• スペードの1 (index = 0)は同じ数字なので右側の最後に移動されます。

xを入れ替えます。markも同じように入れ替えます。
ソート手順2 右側から自分より小さい(同じ値含まない)ものを検索して左側の最後に移動します。

• 右側にいるハートの1は自分と同じ値なので移動は起きません。

結果は以下になります。

x = [1,1,1]
mark=["c","h","s"] # クラブ、ハート、スペード

今回はもう並び替えの必要が無いことがわかるのでこれでおしまいです。
スペード、クラブ、ハートの並びがクラブ、ハート、スペードになってしまいました。
なので不安定です。

単純には元の順序を覚えておいて、並び替え後にそれを使って評価すればいいと思います。
工夫のしどころはありますが、それ書いたら問題の意義が失われるのでそれは自分で考えてください。

Comments

[退会済みユーザー]

回答ありがとうございます。

理解できました。スペードやハート、クラブが、入力した順番に、出力できれば良いのですね。

なので、入力した順番を覚えておいて、出力する必要があるというアルゴリズムが書ければ、正解ということですね。

ありがとうございます。考えて、問題を解いてみたいと思います。

Answer 2

以下のとおりです。

ここでは、同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを、「安定な出力」と呼ぶことにします。（※常に安定な出力を行うソートのアルゴリズムを安定なソートアルゴリズムと言います。）

入力、出力、制約、入力例、出力例を見て理解しないと何も始まりません。
何を入力して、何を出力すべきか理解してください。

Comments

[退会済みユーザー]

回答ありがとうございます。

わかりました。もう一回読み直してみます。