selection sort問題

Question

以下程式對陣列A 的元素A[1]，A[2]，...，A[N] 進行選擇排序（selection sort）：

for (i=1,2,3,...N){
min = i;
for (j=i+1,i+2,i+3,...N){
if (A[j] < A[min])
min = j;
}
swap(A[i],A[min]);
}

如果最內層迴圈裡面的 if 敘述改成 if (A[j] <= A[min])⋯，則是否變成穩定的排序演算法？有人能幫忙解釋一下嗎，謝謝!!!

Answer 1

否! 兩者都是 unstable.

若 N 為 2, A[1] 為 8, A[2] 也為 8, 則第二個程式會把這兩個 8 位置變動.