Sort a stack using recursion

Monday 10 January 2022 10:47 AM Beirut Time · 995

Wajdi Alkayal

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:

is_empty(S) : Tests whether stack is empty or not.

push(S) : Adds new element to the stack.

pop(S) : Removes top element from the stack.

top(S) : Returns value of the top element. Note that this

function does not remove element from the stack.

Input:  -3  <--- Top
        14 
        18 
        -5 
        30 

Output: 30  <--- Top
        18 
        14 
        -3 
        -5

This problem is mainly a variant of Reverse stack using recursion.

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order. Here sorted order is important.

Algorithm

We can use below algorithm to sort stack elements:

sortStack(stack S)
    if stack is not empty:
        temp = pop(S);  
        sortStack(S); 
        sortedInsert(S, temp);

Below algorithm is to insert element is sorted order:

sortedInsert(Stack S, element)
    if stack is empty OR element > top element
        push(S, elem)
    else
        temp = pop(S)
        sortedInsert(S, element)
        push(S, temp)

Illustration:

Let given stack be
-3    <-- top of the stack
14
18
-5
30

Let us illustrate sorting of stack using above example:
First pop all the elements from the stack and store popped element in variable ‘temp’. After popping all the elements function’s stack frame will look like:

temp = -3    --> stack frame #1
temp = 14    --> stack frame #2
temp = 18    --> stack frame #3
temp = -5    --> stack frame #4
temp = 30       --> stack frame #5

Now stack is empty and ‘insert_in_sorted_order()’ function is called and it inserts 30 (from stack frame #5) at the bottom of the stack. Now stack looks like below:

30    <-- top of the stack

Now next element i.e. -5 (from stack frame #4) is picked. Since -5 < 30, -5 is inserted at the bottom of stack. Now stack becomes:

30    <-- top of the stack
-5

Next 18 (from stack frame #3) is picked. Since 18 < 30, 18 is inserted below 30. Now stack becomes:

30    <-- top of the stack
18    
-5

Next 14 (from stack frame #2) is picked. Since 14 < 30 and 14 < 18, it is inserted below 18. Now stack becomes:

30    <-- top of the stack
18
14    
-5

Now -3 (from stack frame #1) is picked, as -3 < 30 and -3 < 18 and -3 < 14, it is inserted below 14. Now stack becomes:

30    <-- top of the stack
18
14
-3    
-5

Implementation:

Below is the implementation of the above algorithm.

// C++ program to sort a stack using recursion
#include <iostream>
using namespace std;
 
// Stack is represented using linked list
struct stack {
    int data;
    struct stack* next;
};
 
// Utility function to initialize stack
void initStack(struct stack** s) { *s = NULL; }
 
// Utility function to check if stack is empty
int isEmpty(struct stack* s)
{
    if (s == NULL)
        return 1;
    return 0;
}
 
// Utility function to push an item to stack
void push(struct stack** s, int x)
{
    struct stack* p = (struct stack*)malloc(sizeof(*p));
 
    if (p == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        return;
    }
 
    p->data = x;
    p->next = *s;
    *s = p;
}
 
// Utility function to remove an item from stack
int pop(struct stack** s)
{
    int x;
    struct stack* temp;
 
    x = (*s)->data;
    temp = *s;
    (*s) = (*s)->next;
    free(temp);
 
    return x;
}
 
// Function to find top item
int top(struct stack* s) { return (s->data); }
 
// Recursive function to insert an item x in sorted way
void sortedInsert(struct stack** s, int x)
{
    // Base case: Either stack is empty or newly inserted
    // item is greater than top (more than all existing)
    if (isEmpty(*s) or x > top(*s)) {
        push(s, x);
        return;
    }
 
    // If top is greater, remove the top item and recur
    int temp = pop(s);
    sortedInsert(s, x);
 
    // Put back the top item removed earlier
    push(s, temp);
}
 
// Function to sort stack
void sortStack(struct stack** s)
{
    // If stack is not empty
    if (!isEmpty(*s)) {
        // Remove the top item
        int x = pop(s);
 
        // Sort remaining stack
        sortStack(s);
 
        // Push the top item back in sorted stack
        sortedInsert(s, x);
    }
}
 
// Utility function to print contents of stack
void printStack(struct stack* s)
{
    while (s) {
        cout << s->data << " ";
        s = s->next;
    }
    cout << "\n";
}
 
// Driver code
int main(void)
{
    struct stack* top;
 
    initStack(&top);
    push(&top, 30);
    push(&top, -5);
    push(&top, 18);
    push(&top, 14);
    push(&top, -3);
 
    cout << "Stack elements before sorting:\n";
    printStack(top);
 
    sortStack(&top);
    cout << "\n";
 
    cout << "Stack elements after sorting:\n";
    printStack(top);
 
    return 0;
}
 
// This code is contributed by SHUBHAMSINGH10

Output:

Stack elements before sorting:
-3 14 18 -5 30 

Stack elements after sorting:
30 18 14 -3 -5

Complexity Analysis:

Time Complexity: O(n2).
In the worst case for every sortstack(), sortedinsert() is called for ‘N’ times recursively for putting element to the right place
Auxiliary Space: O(N)
Use of stack data structure for storing values

Exercise: Modify above code to reverse stack in descending order.

This article is contributed by wajdi kayal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Output:

Stack elements before sorting:
-3 14 18 -5 30 

Stack elements after sorting:
30 18 14 -3 -5

Complexity Analysis:

Time Complexity: O(n2).
In the worst case for every sortstack(), sortedinsert() is called for ‘N’ times recursively for putting element to the right place
Auxiliary Space: O(N)
Use of stack data structure for storing values

Exercise: Modify above code to reverse stack in descending order.

This article is contributed by wajdi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Stack Recursion Programming