**Problem :- **

Implement the **QuickSort** algorithm.

**Solution :- **

**Quicksort** is also known as **partition-exchange sort**. This algorithm first divides the array into smaller sub-arrays
which are recursively sorted to obtain the final sorted array.

**Quicksort** algorithm works as follows :-

Select a **pivot** element from the array & re-order all the elements of the array such that all elements less than **pivot**
are placed towards the left of **pivot** & all elements greater than **pivot** are placed towards the right.

Now, **pivot** element is placed in its correct position in the **sorted** array and we have two sub-arrays.

Now recursively sort the sub-arrays using the same procedure.

**Partitioning algorithm ( to find the pivot element ) :- **

Consider an array of size **n**.

We select the last element of the array ( suppose its **k** ).
Let **'j'** be the iterator. We also maintain a variable **'i'**
which points to the last index in which a value less than **k** was found.

**Initialization** :: **j = start_index & i = j - 1 **

Now, we iterate over the array and compare **k** with each element. If we see an element ( **arr[ j ]** ) <= **k**, we increment **i** & swap
**arr[ i ]** & **arr[ j ]**.

Finally, once the iteration is over, we swap **arr[ i+1 ]** & **k**.
So, last element ( **k** ) is placed in its correct position i.e **i+1** & it acts as the **pivot** element and the array
is partitioned into two sub-arrays.

For e.g, consider the array **{ 7, 4, 5, 2, 3, 19, 11, 6, 9, 12, 8 }**

Here, **k = 8** ( last element ) [ Our aim is to place **8** into its correct position in the sorted array ]

Also, **j = 0** ( start index of the array ) & **i = ( j - 1 ) = -1**

We iterate over the array and do **increment of 'i' & swapping** as illustrated above whenever **arr[ j ] <= k**.

After iteration is over, array becomes **{ 7, 4, 5, 2, 3, 6, 11, 19, 9, 12, 8 }** with **i = 5**.

Now, we swap **arr[ i+1 ]** & **k**. So the array becomes **{ 7, 4, 5, 2, 3, 6, 8, 19, 9, 12, 11 }**.

Thus, **pivot element = 8** & **pivot index = ( i + 1 ) = 6 ** and the array is partioned into two sub-arrays

**{ 7, 4, 5, 2, 3, 6 }** & **{ 19, 9, 12, 11 }**

**QuickSort Demonstration :- **

Consider the same array **{ 7, 4, 5, 2, 3, 19, 11, 6, 9, 12, 8 }**. Lets see how **QuickSort** works :-

**After first partitioning :-**

**{ 7, 4, 5, 2, 3, 6 }** ** 8 ** **{ 19, 9, 12, 11 }** ( **8** is the pivot element )

**After partitioning sub-arrays :-**

**{ 4, 5, 2, 3 }** **6** **{ 7 }**
** 8 ** **{ 9 }** **11** **{ 12, 19 }** ( **6** & **11** are pivot elements for the two sub-arrays )

**As we partition further:-**

**{ 2 }** **3** **{ 4, 5 }**
**6** **{ 7 }** ** 8 ** **{ 9 }** **11**
**{ 12, 19 }**

In this way, after repeated partitioning & recursively sorting the sub-arrays we get the final sorted array

**{ 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19 }**

**Complexity** of the **Quicksort** algorithm is **O(n log n)** in average case. However, in worst case it is **O(n ^{2})**,

though this behaviour is very rare.

**#include<iostream>**
**using namespace** std;
*// Display the Array*
**void** displayArray(**int** arr[],**int** size) {
**int** i;
**for** (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}
*// swap elements in the array*
**void** swap(**int** arr[],**int** idx1,**int** idx2) {
**int** temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
*// partition the array into halves s.t that pivot element
// gets stored at it's correct position in the sorted subarray *
**int** partition(**int** arr[],**int** start_idx,**int** end_idx) {
**int** k = arr[end_idx];
**int** i = start_idx - 1;
**int** j;
*// iterate over the subrray *
**for** (j=start_idx;j<end_idx;j++) {
**if** (arr[j] <= k) {
i++;
swap(arr,i,j);
}
}
swap(arr,i+1,end_idx);
*// return the position of pivot element*
**return** i+1;
}
*// quicksort the array recursively *
**void** quickSort(**int** arr[], **int** start_idx, **int** end_idx) {
**int** pivot; *// pivot element *
**if** (start_idx < end_idx) {
pivot = partition(arr, start_idx, end_idx);
*// recursively sort both the partitions*
quickSort(arr, start_idx, pivot - 1);
quickSort(arr, pivot + 1, end_idx);
}
}
*// main*
**int** main() {
**int** arr[] = {7,4,5,2,3,19,11,6,9,12,8};
**int** size = **sizeof**(arr)/**sizeof**(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
quickSort(arr,0,size-1);
cout<<"\nSorted Array :: ";
displayArray(arr,size);
cout<<endl;
**return** 0;
}