Quicksort is an algorithm use divide and conquer approach in which the array is split into subarrays by selecting value from array as pivot and then the sub-arrays are recursively called to sort the elements.

Steps for quick sort are

1. Pick an element from an array called a pivot. (Different versions of Quicksort pick pivot in different ways)

2. Partitioning- Divide the array into two parts in which all elements with values less than the pivot come before the pivot and all elements with values greater than the pivot come after it.

3. Recursively- apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Example

Let say we have an array of numbers ” {8, 6 ,4 ,2 ,9, 5}”, and sort the array in ascending order

Step 1-

We can choose any element from the array as the pivot element.

Here, we have taken the left most (i.e. 8 the first element) of the array as the pivot element.

Step 2-

The elements smaller than the pivot element are put on the left and the elements greater than the pivot element are put on the right.

{5, 6, 2, 4, 9, 8}

Step -3

Recursively perform the operation on above array to sort the array

{ 2, 4, 5, 6, 8, 9}

Quick Sort Example in C#