Generic Quick Sort Algorithm in C#

Generic Quick Sort Algorithm in C#

Example on how to use an efficient sorting algorithm, known as quicksort, in conjunction with generics.

The completed example uses a widget class/object to show how a complex comparison function can easily perform very advanced sorting operations for objects. The generic sorter inherits from List<T> with T being the type.

List.Sort Method (Generic Comparison)

http://msdn.microsoft.com/en-us/library/w56d4y5z.aspx

Now I know some will say why not just use the given List.Sort method that is provided. This tip is geared for those that actually want to see how one goes about coding a quick sort algorithm. Basically, this is a how did they do it, so someone can recode the concepts shown in C or some other language with a proof of concept in a easy programming language such as C#. This also opens the door for more advanced sorting algorithms to be explored, maybe for very large data sets. The stopwatch class can be used to further explorer efficiency.

Also, the more complicated example shows how to use a very complex Compare function to perform advanced sorting. I'll get more into that later. And show where I made one mistake when I first coded the Comparer. That is why module testing is so important.

I'll first show a very basic list of numbers and sort them explaining along the way to show how the code functions.

private static int Compare1(int x, int y)
{
    return x.CompareTo(y);
}
static void Main(string[] args)
{
    QuickList<int> listOfNumbers = new QuickList<int> { 52, -1, 63, 12, 5, 11 };
    listOfNumbers.QSort(Compare1);
}

The quicksort is considered to be very efficient, with its "divide and conquer" algorithm. This sort starts by dividing the original array into two sections (partitions) based upon the value of the first element in the array.

With an unsorted list calling QSort first takes some basic steps. The comparison cannot be null and a list with one or no elements definitely does not need to be sorted. The next step calls a private method 'quicksort' which recursively calls itself to get the job done very efficiently.

Upon entering quicksort for the first time top is 0 and bottom is 5. Partition is a private helper function that actually sorts the List based on the outcome of the comparison function for the given range (partition of the list) and also returns the subscript 'j', the middle of the partition.

First pass: (top = 0, bottom = 5, returns 3)
11, -1, 5, 12, 63, 52

Sorts first section:
{5, -1, 11,} 12, 63, 52 (top = 0, bottom = 3, returns 1)
{-1, 5,} 11, 12, 63, 52 (top = 0, bottom = 1, returns 0)
-1, 5, {11, 12,} 63, 52 (top = 2, bottom = 3, returns 2)

Sorts second section:
-1, 5, 11, 12, {52, 63} (top = 4, bottom = 5, returns 4)
(no more to sort after this point)

At this point the list has been sorted according to the comparison function which basically puts them in order from least to greatest. The final result is:

-1, 5, 11, 12, 52, 63

The static function which I am calling the comparison function basically returns -1 if x is less than y, or zero if they are the same and 1 if x is greater than y.

Now that we have the basic concept of how quicksort functions we can now look at more complicated objects. Also, because this list is generic we can make any list such as List<Foo> = new List<Foo>();

Let's begin with an object called Widget for lack of a better name and provide some sorting rules:

//  The goal of the new factory widget is to sort the widgets by the following guidelines:
//
// 0xAAA1_XXXX - Must appear on the top (X means don’t care)
// 0xBAD1_XXXX - Must appear on the bottom
// 0xXXXX_XXXX - Must appear in the middle, sorted in numeric order
// The output should look like the following:
//
//Before:
//01 : BAD10002
//02 : AAA10002
//03 : BAC30002
//04 : 00000002
//05 : BAD10001
//06 : FFFF0000
//07 : BAD10003
//08 : AAA10003
//09 : 00000001
//10 : BBD20005
//After:
//02 : AAA10002
//08 : AAA10003
//09 : 00000001
//04 : 00000002
//03 : BAC30002
//10 : BBD20005
//06 : FFFF0000
//05 : BAD10001
//01 : BAD10002
//07 : BAD10003

Below is the full listing of the example program that gets the job completed. As you can see the only thing that has changed is the comparison function with the addition of our class called Widget. Widget has only two members Pattern and ID. ID is just a place holder so we can see the reordering. The comparison function has some basic null checking with the brains shown below.

uint xPart = x.Pattern >> 16;
uint yPart = y.Pattern >> 16;
// put custom code here as needed
if (xPart == 0xBAD1 && yPart != 0xBAD1)
{
    return 1; // force x to move down
}
else if (xPart != 0xBAD1 && yPart == 0xBAD1)
{
    return -1; // force y to move down (x up)
}
else if (xPart == 0xAAA1 && yPart != 0xAAA1)
{
    return -1; // force x to move up
}
else if (xPart != 0xAAA1 && yPart == 0xAAA1)
{
    return 1;// force y to move up (x down)
}
else
{
    return x.Pattern.CompareTo(y.Pattern); // use normal comparor, even when both are BAD1 or AAA1
}

public class Widget
{
    public uint ID;
    public uint Pattern;
    public Widget(uint id, uint pattern)
    {
       ID = id;
       Pattern = pattern;
    }
}

The comparison function first shifts both patterns to the right that are going to compared into two temporary variables, this ignores the lower bits. 0xBAD1's are forced to the end of the list and 0xAAA1's are forced to the beginning of the list else the basic comparer is used to compare like before (even if both are 0xBAD1 and if both are 0xAAA1). You can run the program to see the results.

The mistake I made is shown below. I will leave it to the user to determine what that mistake is and why the list is not correctly ordered. I commented out a section so the error would be obvious when testing.

// put custom code here as needed
if ((x.Pattern & 0xBAD10000) == 0xBAD10000 && (y.Pattern & 0xBAD10000) != 0xBAD10000)
{
     return 1; // force x to move down
}
else if ((x.Pattern & 0xBAD10000) != 0xBAD10000 && (y.Pattern & 0xBAD10000) == 0xBAD10000)
{
     return -1; // force y to move down (x up)
}
/*else if ((x.Pattern & 0xAAA10000) == 0xAAA10000 && (y.Pattern & 0xAAA10000) != 0xAAA10000)
{
     return -1; // force x to move up
}
else if ((x.Pattern & 0xAAA10000) != 0xAAA10000 && (y.Pattern & 0xAAA10000) == 0xAAA10000)
{
     return 1;// force y to move up (x down)
}*/
else
{
     return x.Pattern.CompareTo(y.Pattern); // use normal comparor, even when both are BAD1 or AAA1
}

Completed QuickSort Example

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
    class Program
    {
        #region My Comparison
        private static int CompareMyList(Widget x, Widget y)
        {
            if (x == null)
            {
                if (y == null)
                {
                    // If x is null and y is null, they're
                    // equal. 
                    return 0;
                }
                else
                {
                    // If x is null and y is not null, y
                    // is greater. 
                    return -1;
                }
            }
            else
            {
                // If x is not null...
                //
                if (y == null)
                // ...and y is null, x is greater.
                {
                    return 1;
                }
                else
                {
                    uint xPart = x.Pattern >> 16;
                    uint yPart = y.Pattern >> 16;

                    // put custom code here as needed
                    if (xPart == 0xBAD1 && yPart != 0xBAD1)
                    {
                        return 1; // force x to move down
                    }
                    else if (xPart != 0xBAD1 && yPart == 0xBAD1)
                    {
                        return -1; // force y to move down (x up)
                    }
                    else if (xPart == 0xAAA1 && yPart != 0xAAA1)
                    {
                        return -1; // force x to move up
                    }
                    else if (xPart != 0xAAA1 && yPart == 0xAAA1)
                    {
                        return 1;// force y to move up (x down)
                    }
                    else
                    {
                        return x.Pattern.CompareTo(y.Pattern); // use normal comparer, even when both are BAD1 or AAA1
                    }
                }
            }
        }
        #endregion

        public class Widget
        {
            public uint ID;
            public uint Pattern;

            public Widget(uint id, uint pattern)
            {
                ID = id;
                Pattern = pattern;
            }
        }

        static void Main(string[] args)
        {
            QuickList<Widget> list = new QuickList<Widget>
            {
                new Widget(1, 0xBAD10002),
                new Widget(2, 0xAAA10002),
                new Widget(3, 0xBAC30002),
                new Widget(4, 0x00000002),
                new Widget(5, 0xBAD10001),
                new Widget(6, 0xFFFF0000),
                new Widget(7, 0xBAD10003),
                new Widget(8, 0xAAA10003),
                new Widget(9, 0x00000001),
                new Widget(10,0xBBD20005),
            };

            Console.WriteLine("Before:");
            Print(list);

            list.QSort(CompareMyList);

            Console.WriteLine();
            Console.WriteLine("After:");
            Print(list);

            Console.ReadKey();
        }

        public static void Print(QuickList<Widget> list)
        {
            for (int i = 0; i < list.Count; i++)
            {
                Console.WriteLine(string.Format("{0:d2} : ", list[i].ID) + string.Format("{0:X8} ", list[i].Pattern));
            }
        }
    }

    /// <summary>
    /// Generic List for quick sorting by a custom comparison function
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class QuickList<T> : List<T>
    {
        /// <summary>
        /// The quicksort is considered to be very efficient,  with its "divide and conquer" 
        /// algorithm.  This sort starts by dividing the original array into two sections 
        /// (partitions) based upon the value of the first element in the array.
        /// This algorithm uses recursion to complete the sorting.
        /// See : http://mathbits.com/mathbits/compsci/arrays/Quick.htm
        /// Best case - O(n log n)
        /// Average case - O(n log n)
        /// Worst case - O(n^2)
        /// </summary>
        /// <param name="_comparison">Custom comparor used for type T</param>
        public void QSort(Comparison<T> _comparison)
        {
            if (_comparison == null) throw new Exception("Comparison cannot be null.");
            if (this.Count < 2) return;
            this._comparor = _comparison;
            this.quicksort(0, this.Count - 1);
            this._comparor = null;
        }

        #region Quick Sort recursive with Comparison function

        private Comparison<T> _comparor = null;
        private void quicksort(int top, int bottom)
        {
            if (top < bottom)
            {
                int middle = partition(top, bottom);
                quicksort(top, middle);   // sort first section
                quicksort(middle + 1, bottom);    // sort second section
            }
        }

        private int partition(int top, int bottom)
        {
            T x = this[top];
            int i = top - 1;
            int j = bottom + 1;

            do
            {
                do
                {
                    j--;
                } while (_comparor(x, this[j]) < 0);

                do
                {
                    i++;
                } while (_comparor(x, this[i]) > 0);

                if (i < j)
                {
                    T temp = this[i];
                    this[i] = this[j];
                    this[j] = temp;
                }
            } while (i < j);
            return j;           // returns middle subscript  
        }

        #endregion
    }
}