Testing sorting algorithms

Some time ago I had to deal with sorting algorithms. Besides my main task I found a good way how to test custom sorting algorithms. This blog entry is one of early birds, more about sorting algorihtms is coming soon. Hopefully some time after TechEd 2007 for Developers. The procedure I wrote to test sorting algorithms is simple and works. Of course, I am always opened for better ideas if somebody wants to suggest some. Here’s the little overview about what I’ve done.

Is array sorted?

At first, let’s look at method that checks if array is sorted or not. To make things simpler I expect that all members in array implement IComparable interface. This expectation has very strong point: it is easy to compare objects of classes that have comparison operators defined but it is impossible to compare objects of classes that doesn’t have those operators defined. To make my method as universal as possible I move comparison logic out of it.

About implementation. Don’t look for any highly respected architectural decisions from this example. This is example about testing, not about nice and respected architecture. But here is my IsSorted() method.


public static bool IsSorted<T>(T[] array) where T : IComparable<T>
{
   
if
(array.Length <= 1)
       
return true
;

   
for (int
i = 1; i < array.Length; i++)
       
if
(array[i - 1].CompareTo(array[i]) >= 0)
           
return false
;
   
return true;
}

The other point I found mentally interesting is question about empty array – is it sorted or not? 🙂

Testing IsSorted() method

As a next step let’s write test for IsSorted() method. In this example I’m using Int32 as a type of arrays to test. Of course you can use any other types you need. To make our tests better we test IsSorted() method with array that contains some elements with same values. Then we can be sure that we can find also CompareTo() methods that make comparisons incorrectly somewhy. And one note – I’m using NUnit for tests.

I wrote to tests – one test for sorted array and the other for unsorted array. In this case we see behavior of IsSorted() for both cases that may occure. The tests are as follows.


[Test(Description = "Integer array is sorted")]
public void
TestInt32ArrayIsSorted()
{
   
Assert.IsTrue(Program.IsSorted<int>(new int
[] { 10, 20, 20, 120 }));
}

[
Test(Description = "Integer array is not sorted")]
public void
TestInt32ArrayIsNotSorted()
{
   
Assert.IsFalse(Program.IsSorted<int>(new int[] { 10, 1, 44, 44 }));
}

Now we can be sure that isSorted() method will be tsted against sorted and unsorted arrays. Before we can test sorting algorithms we need to write some tests more.

Testing comparisons

Specially in the case of custom objects with comparers we need to test if comparers are working well. If they don’t we may get wrong results from other tests. So let’s test them now.


[Test(Description = "Integer is less than other")]
public void
TestInt32LessThan()
{
   
int
i = 2;
   
Assert
.Less(i.CompareTo(3), 0);
}

[
Test(Description = "Integer is greater than other")]
public void
TestInt32GreaterThan()
{
   
int
i = 2;
   
Assert
.Greater(i.CompareTo(1), 0);
}

[
Test(Description = "Integers are equal")]
public void
TestInt32Equal()
{
   
int
i = 1;
   
Assert.AreEqual(i.CompareTo(1), 0);
}

Now we can make sure comparisons are tested and if something went wrong our tests will tell us so.

Sorting algorithm

Now let’s write sorting algorithm we want to test. I have many algorithms and I selected SelectionSort() for this example. Here’s the code.


public static void SelectionSort<T>(T[] array) where T : IComparable<T>
{
   
int
i, j, min;
    T temp;

   
for
(i = 0; i < array.Length - 1; i++)
    {
        min = i;
       
for
(j = i + 1; j < array.Length; j++)
           
if (array[j].CompareTo(array[min]) < 0)
                min = j;

        temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}

I wrote all my sorting algorithms using generics so I can use the same algorithms with differents types of objects.

Testing Sorting Algorihtm

Now let’s write test for SelectionSort() algorithm using integers.


[Test(Description = "Test selection sort on Int32 array")]
public void
TestInt32SelectionSort()
{
   
int[] array = new int
[] { 10, 2, 34, 76, 23, 34 };
   
Program.SelectionSort<int
>(array);
   
Assert.IsTrue(Program.IsSorted<int>(array));
}

Now we have test for SelectionSort() that uses array of integers. Same way we can test also other sorting algorithms we want because IsSorted() method is not dependent of sorting algorithm we are testing. Also it has no strong dependence of types of objects we are testing because we require that all objects used here implement IComparable interface.


3 thoughts on “Testing sorting algorithms

  • Petar Petrov says:

    What will happen if the array contains duplicates ? Your IsSorted() method will return false and for me the array {1,2,2,2,3} is sorted.

    I think you need to change the comparision from

    (array[i – 1].CompareTo(array[i]) > 0) to

    (array[i – 1].CompareTo(array[i]) >= 0).

  • Gunnar says:

    Thanks Petar, it was my bug. Now it is fixed 🙂

  • Sergey says:

    That’s great, but your procedure can’t guarantee that the sorting function works correctly. What if you algorithm makes all elements that same, or just duplicates some elements? (what happens quite often)

    For example:

    Initial array: 3 1 4 0 9

    Output "sorted" array: 0 1 1 4 9

    IsSorted will return true, but sorting method is wrong! (1 replaced 3 in the output)

Leave a Reply

Your email address will not be published. Required fields are marked *