Click here to Skip to main content
15,313,985 members
Articles / Programming Languages / C#
Article
Posted 26 Oct 2006

Stats

79.5K views
1.2K downloads
21 bookmarked

QuickSort Algorithm using Generics in C# 2.0

Rate me:
Please Sign up or sign in to vote.
1.57/5 (8 votes)
26 Oct 2006CPOL1 min read
A QuickSort algorithm implementation using Generics in C# 2.0.

Screen Shot of test program

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:

C#
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.

License

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

Share

About the Author

MaheshBabu.ap
United States United States
No Biography provided

Comments and Discussions

 
GeneralDo not use the first element for the pivot. Pin
Qwertie16-May-11 18:59
MemberQwertie16-May-11 18:59 
GeneralMy vote of 5 Pin
The_Ant3-Aug-10 15:21
MemberThe_Ant3-Aug-10 15:21 
GeneralMy vote of 1 Pin
Akhil Gurua19-Feb-10 7:38
MemberAkhil Gurua19-Feb-10 7:38 
GeneralQuestionable Performance Pin
AtomicMonster5-Mar-08 5:07
MemberAtomicMonster5-Mar-08 5:07 
GeneralStatic it! Pin
JoanComasFdz30-May-07 22:52
MemberJoanComasFdz30-May-07 22:52 

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

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