0

AOJ 安定なソートに関しての質問です。

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

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

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

1 件の回答 1

1

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

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

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


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

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
2
  • 1
    "=="がアドレスの比較というのは誤りです。設問は、比較対象のデータが"S8"とか"H4"で、含まれる数字を元にソートするという設定です。なので、「数字が等しい」と「文字列が等しい(==)」が別の表記でかかれています。
    – suzukis
    Commented 2020年8月11日 7:35
  • @suzukis 指摘ありがとうございます。該当部分を削除しました。
    – sei0o
    Commented 2020年8月11日 23:20

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。