選択ソート - 安定

Question

スワッピングの代わりに、選択ソートを挿入して安定したソートに変更することができます。私は同じオンラインの次の実装を得ました。

私は、これは以下のために安定したソートされますどのように理解しない

 void selection (int a[], int n) 

    { 
while (--n > 0) { 
    int i, max = n; 

    for (i = 0; i < n; i++) { 
     if (a[i] >= a[max]) 
     max = i; 
    } 

    if (max != n) { 
     int save = a[max]; 

     for (i = max; i < n; i++) 
     a[i] = a[i + 1]; 

     a[n] = save; 
    } 
} 
} 

：5,1（、 （1,0）、（2,0）、（5,0）、（4,0）私は上記の実装では、私が見るいけない、（2,0）、（4,0）、（5,1）、（5,0）

を （1,0）を与える言及したと思います）

これは私が理解するように安定した行動として。私は正しいですか？もしそうなら、どうすれば安定した選択ソートを実装できますか？

次のコードを変更すると、安定した選択ソートができます。私が間違っているなら、私を訂正してください。

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

この行は私が思っている望ましい結果を与えません。この場合、ソートのために与えたデータには安定した結果が得られません。私は次のコードはうまくいくと思います。

for (i = 0; i <= n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

私が間違っていれば私を訂正しますか？

ありがとうございました

Answer 1

あなたが投稿したコードは安定した並べ替えのようです。

選択ループでは、の最後のの最大値の出現が常に選択されます。これは、a[i] > a[max]ではなく、a[i] >= a[max]と表示されるためです。

for (i = 0; i < n; i++) { 
    if (a[i] >= a[max]) 
    max = i; 
} 

選択された要素は、最後に配置されます（安定した並べ替えで配置する必要があります）。残りの要素の順序は、スワップではなくすべて移動されるため、変更されません。これにより、等しい値を持つ要素が同じ順序、つまり安定した並べ替えにとどまることが保証されます。