Click here to Skip to main content
Click here to Skip to main content

Generic Quick Sort Algorithm in C#

, 26 Mar 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
How generics can be used to sort lists easily and efficiently.
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
    }
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

jc3po
Software Developer (Senior)
United States United States
jciii@earthlink.net

Comments and Discussions

 
QuestionCheck this Pinmemberxtreme performer27-Feb-13 4:20 
GeneralNot clear PinmentorHans Dietrich27-Mar-11 9:13 
You say This tip is geared for those that actually want to see how one goes about coding a quick sort algorithm. However, you include only a few sentences about what your algorithm is doing, and your examples - and the explanation - are not very clear. This article is little more than a code dump. If you intend for it to be an explanation of quick sort, then explain it, don't just nibble at the edges.
 
Here are some questions I would like to see discussed:
  1. What compromises did you make while coding it?
  2. What tradeoffs between speed and memory?
  3. What assumptions does your algorithm make?
  4. How does your algorithm compare to the ones published by Knuth et al?
  5. What problems did you run into while implementing your algorithm?
 
On the plus side, I'm glad that you're interested in explaining code. Please update your article, from the standpoint of explaining your algorithm to another developer, face to face. I'm sure that would be very interesting to read!
Best wishes,
Hans
 

[Hans Dietrich Software]

GeneralJust fyi... PinmemberAndrew Rissing23-Mar-11 6:52 
GeneralRe: Just fyi... Pinmemberjc3po26-Mar-11 8:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.141015.1 | Last Updated 26 Mar 2011
Article Copyright 2011 by jc3po
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid