Selection sort - Swap with next smallest vs smallest overall

Question

I have a question about selection sort. In the below example -

12 8 7 5 2

will the next step be

8 12 7 5 2

or

2 8 7 5 12

?

The reason being that from the pseudocode, it seems that we simply look for the first element having a value smaller than the existing first rather than the smallest overall. So by that logic, the element to be swapped with 12 should be 8 instead of 2, right?

This is the pseudocode I am working with -

static int[] selectionSort(int[] input) {
    if (input.length == 0) {
        return null;
    }
    else {
        int pos = -1;
        for (int i=0;i<input.length-1;i++) {
            pos = i;
            for (int j=i+1;j<input.length;j++) {
                if (input[j] < input[pos]) {
                    int temp = input[pos];
                    input[pos] = input[j];
                    input[j] = temp;
                }
            }
        }
    }
    return input;
}

Is there something wrong with my understanding? Which of the 2 steps would be the correct one? The code should ideally result in the first option, shouldn't it?

Thanks!

Answer 1

In selection sort, you need find out the minimum element in the remaining array and swap those two.

So in your example, next step should be 2 8 7 5 12. The only change needed in your code is to defer the swapping till the end, so only the smallest element will be swapped.

static int[] selectionSort(int[] input) {
    if (input.length == 0) {
        return null;
    }
    else {
        int pos = -1;
        for (int i=0;i<input.length-1;i++) {
            pos = i;
            for (int j=i+1;j<input.length;j++) {
                if (input[j] < input[pos]) {
                    pos = j;
                }
            }
            int temp = input[pos];
            input[pos] = input[i];
            input[i] = temp;
        }       
    }
    return input;
}