Sorting array using Stacks

Problem statement

The problem “Sorting array using Stacks” states that you are given a data structure array a[ ] of size n. Sort the elements of the given array using stack data structure.

Example

2 30 -5 43 100

-5 2 30 43 100

Explanation: The elements are sorted in ascending order.

2 3 1 8 6

1 2 3 6 8

Approach for Sorting array using Stacks

Create a stack data structure to store all the elements of the given input array a[ ]. After that, create another temporary stack for sorting the original one. Iterate through the original stack and for each element pop the top and store it in a temporary variable. Similarly, iterate through the temporary stack while the element at top of the temporary stack is less than the popped top of the original stack. Insert the top element of the temporary stack in the original stack and remove it from the temporary stack. Push the popped top of the original stack in the temporary stack. In the end, the temporary stack will contain elements in sorted order. This problem is a slight modification over sort a stack using temporary stack.

Algorithm

1. Initialize an array a[ ] of size n.
2. Create a stack data structure. Traverse through the array a[ ] and push all the elements of the array a[ ] in the stack.
3. Similarly, create another temporary stack.
4. Traverse while the size of the original stack is not 0. Create a variable tmp and store the element at the top of the original stack in it and pop it from the original stack.
5. Again traverse while the temporary stack is not empty and pop the element at the top of the temporary stack until it is less than the variable tmp. While popping from temporary stack, push the top element of the temporary stack in the original stack.
6. Push the variable tmp in a temporary stack.
7. Traverse from 0 to n-1 and store the top element of the temporary stack in array a[ ] at the current index and pop/delete the element from the temporary stack.
8. Finally, Traverse from 0 to n-1 and print the array a[ ].

Code

C++ Program for Sorting array using Stacks

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(stack<int> input){ 
    stack<int> tmpStack; 
    while(!input.empty()){ 
        int tmp = input.top(); 
        input.pop(); 
  
        while (!tmpStack.empty() && tmpStack.top() < tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}

-5 2 30 43 100

Java Program for Sorting array using Stacks

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}

-5 2 30 43 100

Complexity Analysis

Time Complexity

O(n^2) where n is the number of elements in the stack. Since we are pushing the elements back from the temporary stack to the original stack in case the top of the temporary stack is lesser than the element to be pushed. For better understanding, consider a descending order sequence and try to run the algorithm.

Space Complexity

O(n) because we used temporary stack space for n elements. The space used by the original stack is not counted for the algorithm.