QuickSort algorithm Implementation in C#

QuickSort is one of the most popular sorting algorithms.It is based on the principle of divide and conquer.In simple words Quicksort uses partition based on pivot to sort an array.Elements in one array are greater than the pivot element while elements in the other array are smaller than the pivot element.The algorithm calls itself recursively.

There are two main functionalities in QuickSort algorithm:

Partition algorithm  It divides elements into smaller and larger elements based on the pivot

Sorting algorithm  It calls itself by passing the following parameters:

• Beginning value
• Ending value
• Pivot Index

In simple words Partition algorithm can be described as:

1. Pass low index and high index along with array.If the array has 5 elements then low index will be 0 and high index will be 4.
2. Set pivot element at any position in the array.For example you can set pivot to first element,middle element or last element.
3. Initialise tracking Index variable which represents the number of exchanges made in the array.This should be initialised to 0.
4. Loop from low index to high index.So in this case loop from index = 0 to index = 5
5. If current element is less than or equal to pivot then exchange the current element with the element at tracking Index.
6. Exchange tracking variable with the element at high index

Quciksort algorithm can be described as:

1. Pass the array and the begin and end parameters.begin and end are the beginning and end of the array which we want to
   partition.
2. Call partition method and fetch index returned by it.
3. Call quick sort two times.First call it by passing array ,low and pivot -1
4. Secondly call it with array,pivot+1 and high

You can implement QuickSort in C# as:

static int PartitionArray(int[] arr, int beginingIndex,int endIndex)
{
int pivot = arr[endIndex];

int swapIndex = (beginingIndex - 1);
for (int elementIndex = beginingIndex; elementIndex < endIndex; elementIndex++)
{
//compare pivot element
if (arr[elementIndex] <= pivot)
{
swapIndex++;

// swap arr[i] and arr[j]
int temp = arr[swapIndex];
arr[swapIndex] = arr[elementIndex];
arr[elementIndex] = temp;
}
}

int temp1 = arr[swapIndex + 1];
arr[swapIndex + 1] = arr[endIndex];
arr[endIndex] = temp1;

return swapIndex + 1;
}

public static void QuickSort(int[] arrObj, int beginIndex, int endIndex)
{
if (beginIndex < endIndex)
{

int pivot = PartitionArray(arrObj, beginIndex, endIndex);

// Recursively call quicksort method
QuickSort(arrObj, beginIndex, pivot - 1);
QuickSort(arrObj, pivot + 1, endIndex);
}
}

 

Follow on: