Minimum number of swaps to sort an array with no duplicates

Question

I want to find the minimal number of swaps to sort an array. (The array is guaranteed not to have duplicates.) I found a post that does this basically using a graph: Compute the minimal number of swaps to order a sequence

But I was wondering if I can also do this by running selection sort and counting the number of swaps. (See code below.) Is this approach correct? Or is there a case where it will give the wrong result?

int minSwaps(int[] A, int n) {
    int numSwaps = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            numSwaps++;
            int temp = A[minIndex];
            A[minIndex] = A[i];
            A[i] = temp;
        }
    }
    return numSwaps;
}

score 0 · Answer 1 · answered May 04 '20 at 15:43

0

Your approach is correct. As Wikipedia explains:

One thing which distinguishes selection sort from other sorting algorithms is that it makes the minimum possible number of swaps, n − 1 in the worst case.

This is true even if the array can contain duplicates.

In fact, your approach is just a special case of the approach at the question you link to. That question doesn't actually use a graph; the answer just uses graph theory to try to prove that the approach works. So the arguments there apply just as well to your approach.

That said, your exact approach requires O(n²) comparisons, whereas other variants of this approach can be done in just O(n log n) time. Only you can decide whether the simplicity of your variant is worth the greater time complexity.

answered May 04 '20 at 15:43

ruakh

175,680
26
273
307

Thanks for the confirmation, I was just wondering if this selection sort approach will fail for some case or not. – Nitin Singhal May 04 '20 at 15:48
@NitinSinghal: Yeah, I know. But I thought you'd appreciate some more information than just that. :-) – ruakh May 04 '20 at 16:23
I noticed one more thing that the mentioned graph theory approach will fail if elements are not in the [1,2,3....n] but this selection sort approach will work – Nitin Singhal May 04 '20 at 16:44
@NitinSinghal: This selection-sort approach is a special case of the approach in that question; so if the selection-sort approach works for arbitrary arrays (and it does), then so does the approach in that question. – ruakh May 04 '20 at 17:33

Minimum number of swaps to sort an array with no duplicates

1 Answers1