QuickSort Algorithm using Generics in C# 2.0

By , 26 Oct 2006

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

A list of licenses authors might use can be found here

 MaheshBabu.ap United States Member
No Biography provided

Votes of 3 or less require a comment

 Search this forum Profile popups    Spacing RelaxedCompactTight   Noise Very HighHighMediumLowVery Low   Layout Open AllThread ViewNo JavascriptPreview   Per page 102550
 First Prev Next
 Do not use the first element for the pivot. Qwertie 16 May '11 - 18:59
 My vote of 5 The_Ant 3 Aug '10 - 15:21
 With a few modifications I had the sort working just some simple changes to fit my class structure. Without any other optimization I was able to sort 10 million ints in a test run in about 12 seconds. Once I optimizated and made some adjustments I was able to preform the same sort in around 6 seconds. This was a great time saver and I did not make too many changes. Thank you! Sign In·View Thread·Permalink
 My vote of 1 Akhil Gurua 19 Feb '10 - 7:38
 Questionable Performance AtomicMonster 5 Mar '08 - 5:07
 I used an implementation that was strictly limited to integers, then I used yours with an integer type, and the performance difference was huge. Given a list of 100,000 values, the int structure completed in 359.375 ms while this method was 2984.375 ms. I'm not sure if this is due to generics or the logic itself, but something is amiss here. For one thing, you are taking the time to copy all the values from one array to another - for 100,000 values, thats a huge timesink. While this gets the job done in terms of sorting, it is not (imho) a good implementation where performance is a concern. But, it is a good example of how to use generics in a standard method. Sign In·View Thread·Permalink
 Static it! k^s 30 May '07 - 22:52
 I think that for having only one private value in the class, you can made it static   Something like this:   public static class QuickSorter where T : IComparable { public static T[] Sort(T[] values) { Sorting(0, values.Length - 1, ref values);   return values; }   private static void Sorting(int beg, int end, ref T[] values) { if (end == beg) { return; } else { int pivot = getPivotPoint(beg, end, ref values); if (pivot > beg) Sorting(beg, pivot - 1, ref values); if (pivot < end) Sorting(pivot + 1, end, ref values); }   }   private static int getPivotPoint(int begPoint, int endPoint, ref T[] values) { int pivot = begPoint; int m = begPoint + 1; int n = endPoint;   while ((m < endPoint) && (values[pivot].CompareTo(values[m]) >= 0)) { m++; }   while ((n > begPoint) && (values[pivot].CompareTo(values[n]) <= 0)) { n--; }   while (m < n) { T temp = values[m]; values[m] = values[n]; values[n] = temp;   while ((m < endPoint) && (values[pivot].CompareTo(values[m]) >= 0)) { m++; }   while ((n > begPoint) && (values[pivot].CompareTo(values[n]) <= 0)) { n--; }   }   if (pivot != n) { T temp2 = values[n]; values[n] = values[pivot]; values[pivot] = temp2;   }   return n; }   } Sign In·View Thread·Permalink
 Last Visit: 31 Dec '99 - 18:00     Last Update: 18 May '13 - 20:19 Refresh 1