Java Notes

Selection Sort

Overview of selection sort

Selection sort description

The selection sort algorithm sorts an array into ascending (or descending) order by dividing an array into two sections: a sorted section at the beginning and an unsorted portion after that. Initially the sorted portion has nothing in it, and the whole array is the unsorted portion.

  1. Find the lowest value in the unsorted portion.
  2. remove it from the unsorted portion and add it to the sorted portion.
  3. Go back to step 1.

To avoid the inefficiencies of removing and inserting array elements, a clever shortcut is used to simply exchange the smallest value with the first unsorted element and move the boundary of the unsorted up one place.

This is easy to program, but isn't the fastest sort. The time selection sort requires goes up as the square of the number of data elements (O(n2), however if you don't have much data, eg fewer than 100 elements, selection sort is perfectly acceptable.

Simple selection sort in Java

Remember the index of the smallest element that it finds in each pass of the inner loop over the unsorted values. After the smallest unsorted value is found, add it to the end of the sorted values by exchanging it with the first unsorted value (which then becomes the last sorted value).

public static void selectionSort1(int[] x) {
    //... i is the first element after the sorted portion of the array.
    for (int i = 0; i < x.length-1; i++) {
        int minIndex = i;      // Index of smallest unsorted value.  Assume first.
        //... Look at the remaining unsorted for something smaller.
        for (int j = i+1; j < x.length; j++) {
            if (x[minIndex] > x[j]) {
                minIndex = j;  // Remember index of new minimum
            }
        }
        //... Move smallest unsorted to front by exchanging it.
        int temp = x[i];
        x[i] = x[minIndex];
        x[minIndex] = temp;
    }
}

Common variation of selection sort.

In the previous selection sort code, an exchange is always made, even if the first unsorted element was the smallest, which would cause an exchange with itself. There's no harm in exchanging an element with itself, but it's a waste of time. The 'if' is certainly slightly faster than the exchange, so this will be faster when the file is already sorted, but it's doubtful that it's worth the 'if'. Remember, you probably should use the faster library sort anyway.

public static void selectionSort2(int[] x) {
    for (int i = 0; i < x.length-1; i++) {
        int minIndex = i;      // Index of smallest unsorted 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) { 
            //... Move smallest unsorted to front by exchanging it.
            int temp = x[i];
            x[i] = x[minIndex];
            x[minIndex] = temp;
        }
    }
}

Extra if. It's a minor point, but the first example will sometimes run faster than the second. Why? If the data is already sorted initially, no exchanges will be made, so all if conditions will be false and therefore useless overhead. The second algorithm executes more if's and would therefore be slower. Data that is already sorted is more common that you might think at first.

Variations