Quick sort in C#

by anonymous

• 0
• 0
• 0
65 views
```Orignal source:http://codingvilla.com/quick-sort-in-csharp-single-article-624.aspx

Quick Sort

Quick sort as its name is the fastest sorting algorithm. It operates by partitioning the array into two sub arrays. We can make its partitions by selecting a pivot point. Thus elements with values greater than pivot value will be placed on pivot’s one side and the elements with values smaller than pivot’s value will be placed on the other side. Quick sort is a recursive technique which calls itself again and again in a program.

How Quick Sort Works

To see how quick sort works let’s examine the following array:

42 89 63 12 94 27 78 3 50 36

First we will consider its pivot point. Let’s suppose it is 36. Then we will do its partition. The elements with values smaller than 36 will come on its right side and the elements with values greater than 36 will come on its left side as:

3 27 12 36 63 94 89 78 42 50

After the partition, there are now two different sub arrays. Quick sort method will recursively call itself to sort the sub arrays.

Algorithm for Quick Sort

public static void Quicksort(IComparable[] elements, int left, int right)
{
int i = left, j = right;
IComparable pivot = elements[(left + right) / 2];

while (i <= j)
{
while (elements[i].CompareTo(pivot) < 0)
{i++; }

while (elements[j].CompareTo(pivot) > 0)
{   j--; }

if (i <= j)
{
// Swap
IComparabletmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;

i++;
j--;
}
}

// Recursive calls
if (left < j)
{
Quicksort(elements, left, j);
}

if (i < right)
{
Quicksort(elements, i, right);
}
}

First pivot point is found and placed in its partition position then the elements of array are compared with pivot value. The elements with smaller values will come on its pivots left side and larger will come on its right side. After the partition, the same algorithm will recursively call itself to sort sub arrays.

Its complexity is O(n x logn).

The following code will show the sorting of array with quick sort algorithm.

Code

class Program
{
static void Main(string[] args)
{
string[] unsorted = { "z","e","x","c","m","q","a"};
for (int i = 0; i <unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}
Console.WriteLine();
Quicksort(unsorted, 0, unsorted.Length - 1);
for (int i = 0; i <unsorted.Length; i++)
{
Console.Write(unsorted[i] + " ");
}
Console.WriteLine();
}
public static void Quicksort(IComparable[] elements, int left, int right)
{
int i = left, j = right;
IComparable pivot = elements[(left + right) / 2];
while (i <= j)
{
while (elements[i].CompareTo(pivot) < 0)
{
i++;
}
while (elements[j].CompareTo(pivot) > 0)
{
j--;
}

if (i <= j)
{

IComparabletmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;

i++;
j--;
}
}

if (left < j)
{
Quicksort(elements, left, j);
}

if (i < right)
{
Quicksort(elements, i, right);
}
}

}
```