QuickSort Algorithm using Generics in C# 2.0

• Download demo project - 13 Kb
• Download source - 4.81 Kb

Introduction

Quick Sort is the fastest sorting algorithm. Quick sort uses the divide and conquer strategy. In this algorithm, I have implemented the Quick Sort algorithm using Generics in C# 2.0.

Background

The Quick Sort algorithm has following steps:

1. If there are one or less elements in the array to be sorted, return immediately.
2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
4. Recursively repeat the algorithm for both halves of the original array.

Using the code

Generics in C# are similar to templates in C++. Using Generics, I can use the same piece of code for sorting int, float, and double. The Generics class for a Quick Sort is as follows:

public class QuickSort <T> where T:IComparable
{
    T[] input;
    
    public QuickSort(T[] values)
    {
        input = new T[values.Length];
        for (int i = 0; i < values.Length; i++)
        {
            input[i] = values[i];
        }
        
    }

    public T[] Output
    {
        get
        {
            return input;
        }
    }
    public void Sort()
    {
        Sorting(0, input.Length-1);
    }
    public int getPivotPoint(int begPoint, int endPoint)
    {
        int pivot = begPoint;
        int m = begPoint+1;
        int n = endPoint;
        while ((m < endPoint) && 
               (input[pivot].CompareTo(input[m]) >= 0))
        {
            m++;
        }

        while ((n > begPoint) && 
               (input[pivot].CompareTo(input[n]) <= 0))
        {
            n--;
        }
        while (m < n)
        {
            T temp = input[m];
            input[m] = input[n];
            input[n] = temp;

            while ((m < endPoint) && 
                   (input[pivot].CompareTo(input[m]) >= 0))
            {
                m++;
            }

            while ((n > begPoint) && 
                   (input[pivot].CompareTo(input[n]) <= 0))
            {
                n--;
            }

        }
        if (pivot != n)
        {
            T temp2 = input[n];
            input[n] = input[pivot];
            input[pivot] = temp2;
            
        }
        return n;

    }
    public void Sorting(int beg,int end)
    {
        if (end==beg)
        {
            return;
        }
        else
        {
            int pivot = getPivotPoint(beg,end);
            if(pivot > beg)
            Sorting(beg, pivot-1);
            if(pivot < end)
            Sorting(pivot+1, end);
        }
    }
}

Points of Interest

The CompareTo method is used for comparing the generic type variables. ‘<’ and ‘>’ cannot be used for comparing generic variables because it works only with certain types. As generic parameter can used as any type of parameter, it will throw a compiler error:

Operator '>' cannot be applied to operands of type 'T' and 'T'.

Operator '<' cannot be applied to operands of type 'T' and 'T'.

Reference

For more information on the Quick Sort algorithm, see here.