|
This post is completed by 2 users
|
Add to List |
421. Sort a given stack - Using Recursion
Objective: Given a stack of integers, write an algorithm to sort the stack using recursion.
Example:
Original Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Original Stack: [4, 9, 6, 8, 10, 5] Sorted Stack is:[10, 9, 8, 6, 5, 4]
Approach:
In this solution, we need two recursive functions. sorting() and sortingUtil().
sorting() - this function will be called by the driver. In this function, Pop the element from the stack make a recursive call to sorting() till the stack is not empty. This will put all the popped elements in the function stack and our stack will be empty, in tail recursion insert all these popped elements in the stack in sorted order using sortingUtil().
sortingUtil(X) - This function is called with element passed as a parameter (Let's say it's X) and objective of this function to insert the X to maintain the sorted order. X can be pushed into the stack on condition - stack is empty OR top element of the stack is greater than the X. If this condition is not met then pop the top element out and make a recursive call to sortingUtil(X). This recursive call is made until the condition for the insertion of X becomes true. All the popped elements will be saved in the function stack. Once X is inserted pushed these elements back to the stack.
Walk Through:
As you can see the sortingUtil() is called 4 times, once for each element. sortingUtil() itself is a recursive function. Let's see what is happening inside the function for one instance. sortingUtil(3) is the last time this function was called and produced our final result as well. let's take a look inside.
Output:
Original Stack: [4, 9, 6, 8, 10, 5] Sorted Stack is:[10, 9, 8, 6, 5, 4]