Home Java Java-tips Data Arrays Selection Sort

Ask Questions?

View Latest Questions

Advertisement


 
 

Selection Sort
Posted on: July 26, 2006 at 12:00 AM
Selection sort is implemented with two nested loops.

Java Notes

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;
        }
    }
}
Copyleft 2005 Fred Swartz MIT License
Advertisement


DMCA.com