69435


[AOJ
安定なソート](http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_2_C&pattern=post&type=general&filter=Algorithm)に関しての質問です。

[code]

    1 isStable(in, out)
    2   for i = 0 to N-1
    3     for j = i+1 to N-1
    4       for a = 0 to N-1
    5         for b = a+1 to N-1
    6           if in[i] と in[j] の数字が等しい && in[i] == out[b] && in[j] == out[a]
    7             return false
    8 return true
    
[/code]

が擬似コードとして示されておりますが、in[i] == out[b] && in[j] ==
out[a]の部分のaとbがなぜ必要なのか、この部分があることによりなぜ判定ができるのかが、考えてもわかりませんでした。

この理由について教えていただければ幸いです。


CC BY-SA 4.0
2020-08-10T20:27:27.070
69433
2020-08-11T23:20:01.947
30396
question
sort
安定なソートかどうかの判定方法について


2番目の変数`j`についてのループが`i+1`から始まっていることに注目します。これは「`i`よりも右にある（後にある）要素について調べていく」ということです。`a`と`b`についても同様に、`b`には`a`よりも右にある要素が入ります。言い換えれば、`i
< j` かつ `a < b` が常に成り立ちます。

そして、`in[i] == out[b]` は「入力された`i`番目の要素がソート結果の`b`番目にあること」、`in[j] == out[a]`
は「入力された`j`番目の要素がソート結果の`a`番目にあること」を示しています。ここで、`a < b`
なので、`i`番目の要素は`j`番目の要素より右に動いたことになります。

ところが、これは安定なソートの定義に矛盾します。安定なソートでは、要素の値が同じときの前後関係（〜が〜よりも右にくる）が維持されるのでした。したがって、この場合ソートは安定でないといえます。

* * *

また、疑似コードは以下のようにも書き換えられます（ループを分けました）。

[code]

    isStable(in, out)
     for i = 0 to N-1
       for j = i+1 to N-1
         if in[i] と in[j] の数字が等しい
           for a = 0 to N-1
             for b = a+1 to N-1
               if in[i] == out[b] && in[j] == out[a]
                 return false
     return true
    
[/code]


CC BY-SA 4.0
2020-08-10T23:09:48.907
69435
2020-08-11T23:20:01.947
2020-08-11T23:20:01.947
7500
7500
69433
answer