Sort an array using stacks

Last Updated on December 14, 2022 by Prepbytes

Problem statement

Given an array of integers of size N , sort it in increasing order using a stack.

Example :
Sample input : 4 2 3 1 5
Sample output: 1 2 3 4 5

Sample input: 8
Sample output: 8

Approach

We want to sort the array in increasing order , to do so we will try to create a monotonic stack which is in decreasing order . We will traverse the array from left to right and push every element into the stack in such a way that the monotonic property is maintained . Then we pop all elements from the monotonic decreasing stack and store them into the array from left to right . As the stack was a decreasing stack ,so the array we will get becomes sorted in increasing order .

A monotonic stack is a stack whose elements are monotonically increasing or decreasing. If the top elements of the stack are less than bottom elements , then it is called decreasing stack , else If the top elements of the stack is greater than the bottom elements , then it is called increasing stack.

Algorithm to sort an array using stacks

1. Create a recursive insert function that inserts a number into the stack at the right positions so as to maintain monotonically decreasing property . Working of insert method is below

   • If the stack is empty or top of stack is greater than the current number than push it into the stack and return
   • Else pop the top of the stack and store it into a variable x and call the insert function recursively
   • At the end of the current call , insert x back into the stack

2. Traverse the array from left to right , and insert every element into the monotonic stack using the insert method we have discussed above . At the end of the traversal we will get a monotonic decreasing stack .

3. Now pop each element from the stack and store them into the array from left to right . The array will be sorted in increasing order .

Dry run of above algorithm

C++ Implementation

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

void insert(stack<int> &st , int num){
	if(st.empty() || st.top() >= num){
		st.push(num);
		return;
	}
	int x=st.top();
	st.pop();
	insert(st,num);
	st.push(x);
}

void sortUsingStack(int array[],int n){
	
	stack<int> st;
	for(int i=0;i<n;i++){
		insert(st,array[i]);
	}
	
	for(int i=0;i<n;i++){
		array[i]=st.top();
		st.pop();
	}
}

int main() {
	int array[5]={4,2,3,1,5};
	int n=5;
	
	cout<<"array before sorting : ";
	for(int i=0;i<n;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
	
	sortUsingStack(array,n);
	
	cout<<"array after sorting : ";
	for(int i=0;i<n;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
	return 0;
}

Time complexity : O(nn)
Each insert call might take O(n) time in the worst case , and we are calling insert function n times . so the overall time complexity in the worst case is O(nn) .

In the best case , time complexity will be O(n) .

Space complexity : O(n) for additional monotonic stack .

This article tried to discuss How to sort an array using stacks. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.