# Quicksort Algorithm with C# program code

Quick Sort C Programming

In the last post we learnt the merge sort algorithm which is based on divide-and-conquer paradigm. Today we are going to learn one more sorting algorithm which is also follows divide-and-conquer paradigm. In quick sort we use a procedure called ‘Partition()‘ which divides array into two part (not necessarily equal) and then we recursively call the quick sort using C procedure on divided arrays.

The Partition() procedure chooses a pivot element and rearranges the array such that all elements smaller than pivot are put before the pivot and all bigger elements are put at the end. By doing so we have actually found the correct position for pivot element. Partition() procedure returns the index of pivot element after rearranging the array.

So we can describe the quick sort algorithm in three simple steps:

1. Find a pivot element form the array.
2. Rearrange the array so that all the elements smaller than pivot comes before and all the element greater than pivot comes after it. After this step the pivot element is in its final position.
3. Recursively apply step 1 and 2 on the divided array.

Time Complexity: Average Case: O(nlogn)     Best Case: O(nlogn)     Worst Case: O(n2)
Auxiliary Space: O(1)

C# Program Code:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 `using` `System;` `using` `System.Collections.Generic;` `using` `System.Linq;` `using` `System.Text;` `namespace` `ProgramsBlog` `{` `    ``class` `quickSortClass` `    ``{` `        ``// Procedure which return pivot index` `        ``int` `partition(``int``[] arr,``int` `start,``int` `end)` `        ``{` `            ``// We assume last element of array as pivot element` `            ``int` `pivot = end;` `            ``int` `i = start, j = end,temp;` `            ``while` `(i < j)` `            ``{` `                ``// traverse the array and find index where element is greater than pivot element` `                ``while` `(i < end && arr[i] < arr[pivot])` `                    ``i++;` `                ``// traverse the array and find index where element is smaller than pivot element` `                ``while` `(j > start && arr[j] > arr[pivot])` `                    ``j--;` `                ` `                ``//exchange elements on indexes found by i and j` `                ``if` `(i < j)` `                ``{` `                    ``temp = arr[i];` `                    ``arr[i] = arr[j];` `                    ``arr[j] = temp;` `                ``}` `            ``}` `            ``// finally put pivot element at its right position in array` `            ``temp = arr[pivot];` `            ``arr[pivot] = arr[j];` `            ``arr[j] = temp;` `            ``// return pivot index` `            ``return` `j;` `        ``}` `        ``// Quick sort procedure` `        ``void` `quicksort(``int``[] arr, ``int` `start, ``int` `end)` `        ``{` `            ``if` `(start < end)` `            ``{` `                ``// find the pivot index` `                ``int` `pivotIndex = partition(arr,start,end);` `                ``// recursivly call itself for array element before pivot index` `                ``quicksort(arr, start, pivotIndex-1);` `                ``// recursivly call itself for array element after pivot index` `                ``quicksort(arr, pivotIndex + 1, end);` `            ``}` `        ``}` `        ``// Main driver function` `        ``static` `void` `Main(``string``[] args)` `        ``{` `            ``int``[] arr = {2,14,12,8,6,9,15,4,5,1,3,11}; ``// array to be sorted` `            ``quickSortClass qs = ``new` `quickSortClass();` `            ``// calling the quicksort procedure` `            ``qs.quicksort(arr, 0, arr.Length - 1);` `            ``// printing the sorted array` `            ``foreach` `(``int` `x ``in` `arr)` `            ``{` `                ``Console.Write(x + ``" "``);` `            ``}` `            ``// pausing console` `            ``Console.ReadKey();` `        ``}` `    ``}` `}`