Java: Selection Sort

NOTE: You should never really write your own sort. Use the java.util.Arrays.sort(...) or java.util.Collections.sort(...).

Like all simple sorts, selection sort is implemented with two nested loops.

Simple selection sort

The basic idea is to look at each element in the array, and for each element look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

public static void selectionSort1(int[] x) {
    int temp;
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) {
                //... Exchange elements
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
        }
    }
}

More efficient selection sort - Move every value only once

This more efficient variation of selection sort remembers the index of the smallest element that it finds in each pass. At the end of each pass it makes one exchange, if necessary. This is more efficient, but you shouldn't be writing sorts!

public static void selectionSort2(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        int minIndex = i;      // Index of smallest remaining value.
        for (int j=i+1; j<x.length; j++) {
            if (x[minIndex] > x[j]) {
                minIndex = j;  // Remember index of new minimum
            }
        }
        if (minIndex != i) { 
            //...  Exchange current element with smallest remaining.
            int temp = x[i];
            x[i] = x[minIndex];
            x[minIndex] = temp;
        }
    }
}