15,313,985 members
Articles / Programming Languages / C#
Article
Posted 26 Oct 2006

79.5K views
21 bookmarked

# QuickSort Algorithm using Generics in C# 2.0

Rate me:
A QuickSort algorithm implementation using Generics in C# 2.0.

## 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'.```

## Share

 United States
No Biography provided