Iterative Implementation of Quicksort

Write iterative version of recursive Quick Sort algorithm.


 
 
In previous post, we have discussed the recursive implementation of Quicksort algorithm. We have seen that we can optimize Quicksort recursion stack by using tail recursion to minimize the recursive depth. Tail recursion makes sure that at most O(log n) space is used by recursing first into the smaller side of the partition, then using a tail call to recurse into the other. Tail recursion should be recognized by the compiler and optimized to its iterative counterpart.

We have also talked about another recursive stack space optimization. The idea was that when the number of elements in sub-array is below some threshold k (perhaps ten elements), we switch to a non-recursive sorting algorithm such as insertion sort or simply stop processing the subarray and later perform insertion sort on it (in O(kn) time) as each element will be at most k positions away from its final sorted position.

But despite these performance boosts, the algorithm remains recursive in nature. Can we convert the algorithm into an iterative one? In this post, its iterative implementation is discussed.

The idea is to use a stack for storing sub-array starting & ending index and for later processing instead of using recursion. Note that the partitioning logic would remain the same.

 
Iterative C++ implementation –
 

Download   Run Code

Output:

-6 -3 1 2 3 5 6 8 9

 
Exercise: Modify above code to print in descending order.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz