Question: Is the following select sort routine for sorting by the kth letter of an array of strings stable? If so, explain why. If not, give a simple example of three or four words on which it fails.
for(int i = n - 1; i > 0; i--) {
int max = i;
for(int j = 0; j < i; j++) if(A[j][k] >= A[max][k]) max = j;
int t = A[i]; // swap what's at i and what's at j
A[i] = A[max];
A[max] = t;
}
Answer: It is not. Consider sorting the sequence ab bb ba aa based on the second character. When i is 3, max is set to 1 and the second and fourth item are swapped to get ab aa ba bb. When i is 2, max is set to 0 and the first and third item are swapped to get ba aa ab bb. When i is 1, max is set to 1 and the array after the swap is aa ba ab bb. We began with ba before aa in the initial sequence, and these are equal in the second character, so a stable sort would have ba before aa in the final sequence.
There's not really a simple fix to this. The problem is that when selection sort swaps the thing it swaps with the maximum may be placed before an equal key. This will destroy the ordering. Selection sort is inherently unstable.