Selection Sort in Java produces incorrect results

Question

I am new to Java and I am trying to write a selection sort program. Below is my code :

public class SelectionSort {
    public static int a[] = {6, 4, 9, 3, 1, 7};

    public static void main(String[] args) {
        int min, i, j;
        for(i = 0; i < a.length - 1; i++) {
            min = i ;
            for(j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j; 
                }
                if (min != i) {
                    int temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;
                }
            }
        }
        for (i = 0; i < a.length; i++) {
            System.out.println("a : " + a[i]);
        }
    }
}

My input array is 6,4,9,3,1,7. The sorted output should be 1,3,4,6,7,9 But the output I am getting is:

a : 3
a : 4
a : 6
a : 7
a : 1
a : 9

I am doing some small mistake which I am unable to figure out. Can anyone please help me fix it?

Answer 1

You are almost there.

The part that swaps elements should be outside the inner loop.

In other words, you need to first find the smallest element in the remainder of the array, and then swap it into the current position. Right now you're swapping as soon as you have found a smaller number, and in the process failing to keep track of the new position of this smaller number.

Another way to fix the code is to keep the swap where it is, but update min after each swap:

if (min !=i) {
    int temp = a[i];
    a[i] = a[min];
    a[min]= temp;
    min = i;       /* Update `min' to reflect the number's new position */
}

This too will work, but is rather inefficient.

P.S. The if (min != i) check is unnecessary since swapping an element with itself is a harmless no-op.