Selection sort (C Sharp)

From LiteratePrograms

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

This is an implementation of selection sort in the C# 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 C# 1.0 and 2.0.

Contents 1 Integer arrays 2 Generic arrays 3 Object arrays 4 Files 5 Performance

Integer arrays

We start with an implementation specifically for integer arrays:

<<integer array sort>>=
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 C# 2.0, we can generalize our integer example by simply replacing the ints with a generic parameter type T:

<<generic array sort>>=
static void selectionSortGeneric<T>(T[] a) where T : IComparable
{
    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 added the where clause "where T : IComparable". Because we can't use selection sort on objects we can't compare using less-than (<), we require that T implement the IComparable interface, which provides a method CompareTo() for determining if one object of type T is less than other.
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.

Unqualified use of IComparable requires the System namespace:

<<using statements>>=
using System;

Object arrays

C# 1.0 does not provide generics, but it does provide object, a sort of variant type that all other types belong to. Thus, if we can sort an array of objects we can sort an arbitrary array. However, since different datatypes need to be compared differently, we also need to supply something to use to compare them that depends on the type. We do this by passing in an object implementing the IComparer interface (not to be confused with IComparable above) which provides a Compare() method for comparing two objects:

<<object array sort>>=
static void selectionSortGeneric(object[] a, IComparer comparer)
{
    for(int sortedSize=0; sortedSize < a.Length; sortedSize++)
    {
        int minElementIndex = sortedSize;
        object 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 IComparer requires the System.Collections namespace:

<<using statements>>=
using System.Collections;

Files

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

<<SelectionSortExample.cs>>=
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 DateTime.Now and time subtraction.

<<test main>>=
public static void Main(String[] args)
{
    int length = int.Parse(args[0]);
    int[] a = new int[length];
    Random r = new Random();
    for(int i=0; i<length; i++)
    {
        a[i] = r.Next();
    }
    DateTime start = DateTime.Now;
    selectionSortIntArray(a);
    Console.WriteLine("Sort time: " + (DateTime.Now - start));
    for (int i = 1; i < length; i++)
    {
        if (a[i] < a[i - 1])
        {
            Console.WriteLine("ERROR");
            return;
        }
    }
}

Performance

The program was compiled with Visual Studio 2005 in Release mode, then pre-JITted using ngen. It was run for various list sizes on a Pentium 4 2.4 GhZ machine under Windows Server 2003. It was compared to the result obtained using the Framework's Array.Sort(), which is a tuned version of quicksort, and also to a version written in C:

List size	10000	25000	50000	75000	100000	250000
Selection sort	0.093	0.625	2.41	5.34	9.53	81.0
Selection sort (C)	0.079	0.407	1.64	3.80	7.58	71.8
Array.Sort()	0.016	0.000	0.00	0.016	0.016	0.047

The C version is from Selection sort (C), modified to time just the sort call, and was compiled using Visual Studio 2005 in Release mode as well and run on the same machine. The times of Array.Sort() appear unusual because they are so small that the timer resolution is not fine enough to accurately measure them. On random data such as this, selection sort performs terribly even for small list sizes, and should never be used.

Download code