# QuickSort in C++ using Recursion

Quicksort in C++ is** divide and conquer method** used to sort an array.

## QuickSort Alogorithm

To understand how quicksort works? You must know what is Pivot element.

Basically, in quicksort,

- we choose a pivot element. Usally we assume
**pivot element = array[startIndex]**. - Now we
**shift all the elements to the left of pivot element**whiich**is less than pivot element**(i.e element < Pivot Element). - Again
**shift all the elements to the right of pivot element which is greater than pivot element**(i.e element > Pivot element) - Here the
**final index of the pivot element is the**divide**point of the array**. Hence, now we have two sub-arrays. - Repeat the process (again from step 1) for the subarrays until sub array has one element.

Note: On starting we assumed pivot element = array[startIndex]. Here **startIndex is the first index of the array or sub-array**.

## 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 | #include <iostream> using namespace std; void quickSort(int [],int , int ); int findPivot(int [],int,int); int main() { int arr[] = {5, -6, 22, 37, 4, -11, 15}; quickSort(arr,0,7); for(int i=0;i<7;i++){ cout << arr[i] << " "; } return 0; } void quickSort(int arr[],int s, int e){ if(e-s < 1){ return; } int p = findPivot(arr,s,e); quickSort(arr,s,p); quickSort(arr,p+1,e); } int findPivot(int arr[],int s,int e){ int newElement = arr[s]; int i = s; int j = e; //Empty while loop to find element smaller than pivot element from right while(i<j && arr[--j] > newElement); arr[i] = arr[j]; //Empty while loop to find element greater than pivot element from left while(i<j && arr[++i] < newElement); arr[j] = arr[i]; arr[i]= newElement; if (j>i) return findPivot(arr,i,j); else return i; } |

## Online Compiler

Here findPivot**(…) function is sorting the array** as stated in the algorithm. And quickSort**(…) function is dividing the array** into sub-arrays at index being returned by findPivot(…) function.

### Output

1 | -11 -6 4 5 15 22 37 |

## Quick Sort Overview:

**In-place Algorithm**(No need of extra arrays).**O(**nlogn**)**-base 2. Array is repeatedly partitioning the array into two halves.**Unstable algorithm**(Interchanging duplicate values, which is useless).

Also check Shell Sort Program Code in C++.