How to Sort a Stack using Recursion

Last Updated on October 3, 2022 by Ria Pathak

First we’ll discuss what is Stack:

Stack follows the principle of LIFO (Last in First out) i.e. element which is inserted at last will be removed first. The operation for insertion of elements in stack is known as Push operation and the operation for deletion of element in stack is known as Pop operation.

Examples 1:
Input: 11 17 -2 5 1

Output: 17 11 5 1 -2

Explanation: The Sorted stack contains elements in descending order from top to bottom of the stack.

Examples 2:
Input: 1 2 3 4
Output: 4 3 2 1

The Recursion uses the stack to complete its task. The stack is a linear data structure that follows a particular order i.e. Last in First Out also known as LIFO.

Algorithm to Sort a Stack using recursion

The idea is quite easy.

1. Firstly, We will pop out the top element of the stack and pass the remaining stack to the same function i.e (recursive call).
2. Continue the above process until the stack becomes empty.
3. The moment the stack becomes empty we will call an insert function to insert the elements again in the stack in sorted order.
4. Insert function inserts the elements at their correct place recursively.

Code:

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

void sortedInsert(stack<int> &s, int element){
    // If the element is greater
    // than the top data of the stack then just push this element into the stack
    //because that's the correct position of this element
    if(s.empty() || element > s.top()){
        s.push(element);
    }
    else{
    // otherwise find the correct position of this element recursively
        int top_element = s.top();
        s.pop();
        sortedInsert(s, element);
        s.push(top_element);
    }
}

// function to sort the stack 
void sortStack(stack<int> &s){
    // pop elements from the stack until the stack becomes empty
    if(!s.empty()){
        int top_data = s.top();
        s.pop();

        // recursive call 
        sortStack(s);

        // insert top_data at correct position in the stack
        sortedInsert(s, top_data);
    }
}

int main(){
    // input stack 
    stack<int> s;
    
    // pushing elements into the stack
    s.push(1);
    s.push(5);
    s.push(-2);
    s.push(17);
    s.push(11);

    // function to sort the stack 
    sortStack(s);

    // print stack

    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}

Output:
17 11 5 1 -2

Dry Run

1. Firstly call the recursive function to pop out the top element.

2. The above process will continue until the stack becomes empty.
   Input: 1 5 -2 17 11

   • Current Top element = 11 (Top element is in the stack frame #1)
   • Current Top element = 17 (Top element is in the stack frame #2)
   • Current Top element = -2 (Top element is in the stack frame #3)
   • Current Top element = 5 (Top element is in the stack frame #4)
   • Current Top element = 1 (Top element is in the stack frame #5)

3. Now the stack is empty. So, we will call the insert function to insert the top element i.e (Element in the stack frame) at its correct position.

4. When the insert function is called, element 1 is passed and currently, the stack is empty so, we will just push this element inside the stack.

5. For the next iteration current element is 5. When 5 is passed to the insert function the insert function compares 5 with the top element of the stack and it will find that the 5 is greater than 1 so it will just push 5 inside the stack.

6. Now current element is -2. When -2 is passed to the insert function. The stack top is 5 and -2 less than 5 hence, we cannot push -2 into the stack right now because it’s not the correct position of this element. So, we will recursively call the sortedinsert() function with the current -2, until it gets to an element where the stack top is smaller than -2 or the stack, becomes empty and then push it.

7. The above step gets repeated for the next element also and the final stack becomes.

This article tried to discuss How to Sort a Stack using Recursion. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.