#### Sorting

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(n2),
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);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
quickSort(arr,0,size-1);
cout<<"\nSorted Array   :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}```