Quick Sort Optimization
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.
This article is focused upon optimizing quick sort algorithm, but to learn more about quick sort in detail, click here.
Technique:
To optimize quick sort to use less memory, the technique is quite simple.
IS TO USE TAIL RECURSION !!
Normally tail recursion is not preferable, but in this case tail recursion is combined with the notion of solving the smallest partition first, which drastically improves the space complexity to O(logn) from O(n).
The Optimized 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 remains the same, which is,
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.But a while loop is introduced, which repeatedly calls partition function and calls the quick sort function which has the smallest partition recursively, until all the partitions are sorted out.
Since the smallest partition is always sorted first, the extra memory is limited to O(logn).
Java Code
Click to visit the source code
