CODEWITHSUNDEEP
javaalgorithmsortingselection-sort
Shivam Bhalla
Shivam Bhalla

Reputation: 1919

Selection sort - Swap with next smallest vs smallest overall

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!

Upvotes: 0

Views: 343

Answers (3)

Rocky Singh
Rocky Singh

Reputation: 667

It will be 2, 8, 7, 5, 12. Selection sort always brings the smallest element out to the left. Think of selection sort as the opposite of bubble sort. Where bubble sort bubbles the largest element to the right, selection sort does the opposite. I hope that helps.

Upvotes: 1

Michael
Michael

Reputation: 44210

You start with:

12 8 7 5 2

You start with no elements in the sorted portion, and you iterate through until you find the smallest in the unsorted portion. Then swap that with the first element in the unsorted portion.

sorted  |  unsorted
2          8 7 5 12

Iterate until you find the smallest, and swap with the first in the unsorted portion:

sorted  |  unsorted
2 5         7 8 12

Repeat a few times (no swaps required because elements are already in order):

sorted  |  unsorted
2 5 7       8 12

sorted  |  unsorted
2 5 7 8     12

sorted  
2 5 7 8 12

So your 2nd example is the correct first move.

Upvotes: 2

Can
Can

Reputation: 622

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;
}

Upvotes: 1

Related Questions