Sort Using Stack

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
Apple

Problem statement

You are given an array ‘arr’ of size ‘N’ consisting of integers. Your task is to sort the array using a stack.

Note: 
Do not use any inbuilt function and other methods to sort the array.
For example: 
You are given ‘arr’ = [3 ,4, 1, 2 5], this array sorted will be [1, 2, 3, 4, 5]. Hence the answer is [1, 2, 3, 4, 5]
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains one integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers representing the element of the array.
Output Format: 
For each test case, print the space-separated integers representing the given array in non-decreasing order.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
0 <= arr[i] <= 10^9

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
5
3 4 1 2 5
7
10 4 20 15 2 6 5
Sample Output 2:
1 2 3 4 5
2 4 5 6 10 15 20
Explanation:
For the first test case, given ‘arr’ = [3, 4, 1, 2, 5], this array sorted will be [1, 2, 3, 4, 5]. Hence the answer is [1, 2, 3, 4, 5].

For the second test case, given ‘arr’ = [10, 4, 20, 15, 2, 6, 5], this array sorted will be [2, 4, 5, 6, 10, 15, 20]. Hence the answer is [2, 4, 5, 6, 10, 15, 20].
Sampe Input 2
2
3
1 2 1
2
5 2
Sample Output 2:
1 1 2
2 5
Hint

Try to use two stacks.

Approaches (1)
Two Stacks

In this approach, we will add all the elements of the array in a stack. We will also maintain another stack which will always be sorted, then whenever we find a number, we will insert in it the sorted stack at its position by popping out the elements before it and storing them in the original stack.

 

We create a function sortStact(stk), which will sort the stk, using another stack.

 

Algorithm:

  • In the function function sortStack(stk)
    • Initialize another stack sortedStack
    • While the stk is not empty
      • Set temp as top of the stk and pop the stk
      • While sortedStact is not empty and top of  sortedStack is less than temp
        • Insert sortedStack.top in stk and pop the sortedStack
      • Insert temp into sortedStack
    • Return sortedStack

 

  • Initialise an empty stack stk
  • Iterate num through arr
    • Insert num into stk
  • Set sortedStack as stackSort(stk)
  • Set sol as all the elements poped from the sortedStack
  • Finally, return sol
Time Complexity

O(N^2), Where N is the number of elements in the array.

 

We are iterating through each element of the array. For each element, in the worst case, we have to make O(N) insertions in the stack. Hence the overall time complexity is O(N^2).

Space Complexity

O(N), Where N is the number of elements in the array.

 

We are maintaining two stacks that will contain all the elements of the array. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Sort Using Stack
Full screen
Console