The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

Algorithms

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.