Introduction to Quick Sort
Quick Sort, like the other sorting algorithms focuses upon arranging the input elements in an order set by the given comparison operator, but what sets it apart from the other sorting algorithms is not just the Divide and Conquer strategy, but the notion of revolving around a pivot point is quite intriguing.
The time complexity and space complexity of this algorithm is O(nlogn) and O(n) respectively but the space complexity can be improved to O(logn) by using simple tail recursion.
To Learn more about optimizing quick sort algorithm, click here.
Key Components
Quick Sort Algorithm has two key components,
i: A pivot point.
ii: Partition around the pivot point.
i: Pivot
The pivot point determines from where to start the sorting process, and therefore it determines the speed of the algorithm. To select pivot point, following strategies can be used:
i: First element in the given input.
ii: Last element in the given input.
iii: Median indexed element in the given input.
iv: Random element in the given input.
v: Element which has the middle/average value approximately in the given input.
Of all these 5 strategies, the last one is the least feasible solution, as finding the averaged value element in the unsorted array consumes both time and memory.
ii: Partition
The main role of partition is to use the pivot point such that the elements having values less than the pivoted value are placed to the left and all the elements having values greater than the pivoted value are placed to the right of the pivot.
This process completes in iteration, dividing the input sequences into smaller and smaller set of inputs, whilst adjusting the pivot point accordingly.
At Each Step, there will be two set of input sequences, namely Left and right input sequences, where the left input sequence will always contains elements having value less than the pivoted element and the right input sequence will always contains elements having value greater than the pivoted element.Understanding Pivot & Partition With An Example
Let’s consider an unsorted sequence with values 5, 8, 6, 8, 9, 2, 7, 6
First element is selected as a pivot i.e. index 0 with a value of 5.
The first iteration of partition will place some of the elements less than 5 to the left and all the elements greater than 5 to the right.
The resultant sequence will be 5,2, 8, 6, 8, 9, 7, 6 and pivot point will be updated to index 2 with a value of 8.
The second iteration of partition will focus on the left partition of the input sequence and will place all the elements less than 5 to the left and all the elements greater than 5 to the right.
The resultant sequence will be 2,5, 8, 6, 8, 9, 7, 6 and pivot point will be updated to index 0 with a value of 2. The function will then return as it has sorted the left part of the input sequence successfully.
Pivot & Partition Code
The above partition code takes following three arguments,
i: data: Int input sequence.
ii: start: Starting index of given input sequence.
iii: end: Ending index of given input sequence.
It starts by taking the first indexed value as the pivot point (referred as pIndex) and iterates from the given start till given end of the input sequence, comparing the current element value with the last indexed value (referred as pValue), for the following condition.
i. If the current element is smaller than the pValue, then both the elements will be swapped and pIndex value will be incremented by 1.
After the comparison has been completed, the function will perform final swap between the latest pIndex valued element and the element at the last index. Finally the pIndex value will be returned and will serve as the bases for further partitioning.
The Quick Sort Function
The above quick sort code takes following three arguments,
i: data: Int input sequence.
ii: start: Starting index of given input sequence.
iii: end: Ending index of given input sequence.
Quick sort is usually implemented using recursion, and therefore the underlying Base condition is set as following,
i. If the starting index is greater than or equal to the last index then the recursion will terminate and the function call will be removed from the stack.The Algorithm starts by calling the partition function to divide the input sequence into left and right partitions and return the pivot point accordingly.
The pivot point serves as the last index for the left partition ( Decremented by 1) and starting index for the right partition and then the quick sort function calls it self iteratively,by dividing the input sequence smaller and smaller until no more division could be performed on the input sequence, sorting the individual partitions accordingly.
Java Code
