Selection sort (Java)

From LiteratePrograms

Other implementations: C | C++ | C# | Erlang | Haskell | Java | Python, arrays

This is an implementation of selection sort in the Java language. Selection sort is a simple but inefficient sort which operates by repeatedly extracting the minimum from the list of remaining unsorted elements until none are left. We show an implementation for integer arrays and two generic implementations for Java 5 and above.

Contents 1 Integer arrays 2 Generic arrays 3 Comparator 4 Files

Integer arrays

We start with an implementation specifically for integer arrays:

<<integer array sort>>=
public static void selectionSortIntArray(int[] a)
{
    for (int sortedSize=0; sortedSize < a.length; sortedSize++)
    {
        find minimum of remaining unsorted list
        swap a[sortedSize] with minimum
    }
}

At any instant the list is storing two sublists: a sorted list of the first sortedSize elements, followed by all remaining unsorted elements. To find the minimum of the remaining elements, we just loop over them keeping track of the smallest one we see:

<<find minimum of remaining unsorted list>>=
int minElementIndex = sortedSize;
int minElementValue = a[sortedSize];
for (int i = sortedSize + 1; i < a.length; i++) 
{
    if (a[i] < minElementValue)
    {
        minElementIndex = i;
        minElementValue = a[i];
    }
}

We then perform the swap, taking advantage of the existing variable minElementValue:

<<swap a[sortedSize] with minimum>>=
a[minElementIndex] = a[sortedSize];
a[sortedSize] = minElementValue;

This completes the integer array sort.

Generic arrays

In Java 5 and above, we can write a sort function for arrays of reference types that implement Comparable:

<<generic array sort>>=
public static <T extends Comparable<? super T>> void selectionSortGeneric(T[] a)
{
    for (int sortedSize=0; sortedSize < a.length; sortedSize++)
    {
        int minElementIndex = sortedSize;
        T minElementValue = a[sortedSize];
        for (int i = sortedSize + 1; i < a.length; i++) 
        {
            if (a[i].compareTo(minElementValue) < 0)
            {
                minElementIndex = i;
                minElementValue = a[i];
            }
        }
        a[minElementIndex] = a[sortedSize];
        a[sortedSize] = minElementValue;
    }
}

Other than converting int to T, there are two main changes here:

1. We've declared the type parameter T as "<T extends Comparable<? super T>>", to ensure that we can compare using compareTo() with other objects of type T
2. We convert the less-than test in the inner loop into a call to compareTo(). compareTo() returns a negative number only if the receiver (object before the dot) is less than the argument.

Comparator

If a datatype does not implement the Comparable interface, or we want it to sort in another ordering, we need to supply something to use to compare them that depends on the type. We do this by passing in an object implementing the Comparator interface which provides a compare() method for comparing two objects:

<<object array sort>>=
public static <T> void selectionSortGeneric(T[] a, Comparator<? super T> comparer)
{
    for (int sortedSize = 0; sortedSize < a.length; sortedSize++)
    {
        int minElementIndex = sortedSize;
        T minElementValue = a[sortedSize];
        for (int i = sortedSize + 1; i < a.length; i++) 
        {
            if (comparer.compare(a[i], minElementValue) < 0)
            {
                minElementIndex = i;
                minElementValue = a[i];
            }
        }
        a[minElementIndex] = a[sortedSize];
        a[sortedSize] = minElementValue;
    }
}

Unqualified use of Comparator requires importing it:

<<using statements>>=
import java.util.Comparator;

Files

We can wrap these three methods up in a class in a C# source (.cs) file for reuse.

<<SelectionSortExample.java>>=
using statements
class SelectionSortExample
{
    integer array sort
    generic array sort
    object array sort
    test main
}

We add a simple test main that uses the Random class to fill an array with a given number of random values and then verifies that the result is ordered after sorting with the first algorithm above. It also times the algorithm using System.currentTimeMillis() and time subtraction.

First, we import Random:

<<using statements>>=
import java.util.Random;

<<test main>>=
public static void main(String[] args)
{
    int length = Integer.parseInt(args[0]);
    int[] a = new int[length];
    Random r = new Random();
    for (int i = 0; i < length; i++)
    {
        a[i] = r.nextInt();
    }
    long start = System.currentTimeMillis();
    selectionSortIntArray(a);
    System.out.println("Sort time in ms: " + (System.currentTimeMillis() - start));
    for (int i = 1; i < length; i++)
    {
        if (a[i] < a[i - 1])
        {
            System.out.println("ERROR");
            return;
        }
    }
}

Download code