Java Notes

Selection Sort

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

Two nested loops. 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) {
    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
                int 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 your own sort - use java.util.Arrays.sort(...)!

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

Why might the second example be more efficient?

The second example only makes one exchange, but the exchanges are fairly quick, so what's the problem? Perhaps more important than the actual exchanges is the effect that any assignment has on the CPU's cache memory. Any change to memory can cause the bottleneck between the CPU and RAM to become more congested. If you are using a multi-core CPU, time may be required to synchronize their caches (depending on the organization). If you are using virtual memory, the effect can be much worse. The general rule is that you should avoid excessive assignments to memory because it makes the underlying hardware run faster.