Sorting array using Stacks

Given an array of elements, task is to sort these elements using stack.

Prerequisites : Stacks

Examples :

Input :  8 5 7 1 9 12 10
Output : 1 5 7 8 9 10 12 
Explanation :
Output is sorted element set

Input :  7 4 10 20 2 5 9 1
Output : 1 2 4 5 7 9 10 20

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We basically use Sort a stack using a temporary stack. Then we put sorted stack elements back to array.

C++

// C++ program to sort an array using stack 
#include <bits/stdc++.h> 
using namespace std; 
  
// This function return the sorted stack 
stack<int> sortStack(stack<int> input) 
{ 
    stack<int> tmpStack; 
  
    while (!input.empty()) 
    { 
        // pop out the first element 
        int tmp = input.top(); 
        input.pop(); 
  
        // while temporary stack is not empty 
        // and top of stack is smaller than temp 
        while (!tmpStack.empty() && 
                tmpStack.top() < tmp) 
        { 
            // pop from temporary stack and 
            // push it to the input stack 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        // push temp in tempory of stack 
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
void sortArrayUsingStacks(int arr[], int n) 
{ 
    // Push array elements to stack 
    stack<int> input; 
    for (int i=0; i<n; i++) 
       input.push(arr[i]); 
  
    // Sort the temporary stack 
    stack<int> tmpStack = sortStack(input); 
  
    // Put stack elements in arrp[] 
    for (int i=0; i<n; i++) 
    { 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
// main function 
int main() 
{ 
    int arr[] = {10, 5, 15, 45}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    sortArrayUsingStacks(arr, n); 
  
    for (int i=0; i<n; i++) 
       cout << arr[i] << " "; 
  
    return 0; 
} 

Java

// Java program to sort an  
// array using stack 
import java.io.*; 
import java.util.*; 
  
class GFG 
{ 
    // This function return 
    // the sorted stack 
    static Stack<Integer> sortStack(Stack<Integer> input) 
    { 
        Stack<Integer> tmpStack =  
                       new Stack<Integer>(); 
      
        while (!input.empty()) 
        { 
            // pop out the 
            // first element 
            int tmp = input.peek(); 
            input.pop(); 
      
            // while temporary stack is  
            // not empty and top of stack 
            // is smaller than temp 
            while (!tmpStack.empty() && 
                    tmpStack.peek() < tmp) 
            { 
                // pop from temporary  
                // stack and push it  
                // to the input stack 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            // push temp in 
            // tempory of stack 
            tmpStack.push(tmp); 
        } 
      
        return tmpStack; 
    } 
      
    static void sortArrayUsingStacks(int []arr,  
                                     int n) 
    { 
        // push array elements 
        // to stack 
        Stack<Integer> input =  
                       new Stack<Integer>(); 
        for (int i = 0; i < n; i++) 
            input.push(arr[i]); 
      
        // Sort the temporary stack 
        Stack<Integer> tmpStack =  
                       sortStack(input); 
      
        // Put stack elements 
        // in arrp[] 
        for (int i = 0; i < n; i++) 
        { 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    // Driver Code 
    public static void main(String args[]) 
    { 
        int []arr = {10, 5, 15, 45}; 
        int n = arr.length; 
      
        sortArrayUsingStacks(arr, n); 
      
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
    } 
} 
  
// This code is contributed by  
// Manish Shaw(manishshaw1) 

/div>

C#

// C# program to sort an  
// array using stack 
using System; 
using System.Collections.Generic; 
  
class GFG 
{ 
    // This function return 
    // the sorted stack 
    static Stack<int> sortStack(Stack<int> input) 
    { 
        Stack<int> tmpStack = new Stack<int>(); 
      
        while (input.Count != 0) 
        { 
            // pop out the 
            // first element 
            int tmp = input.Peek(); 
            input.Pop(); 
      
            // while temporary stack is  
            // not empty and top of stack 
            // is smaller than temp 
            while (tmpStack.Count != 0 && 
                    tmpStack.Peek() < tmp) 
            { 
                // pop from temporary  
                // stack and push it  
                // to the input stack 
                input.Push(tmpStack.Peek()); 
                tmpStack.Pop(); 
            } 
      
            // push temp in 
            // tempory of stack 
            tmpStack.Push(tmp); 
        } 
      
        return tmpStack; 
    } 
      
    static void sortArrayUsingStacks(int []arr,  
                                     int n) 
    { 
        // Push array elements 
        // to stack 
        Stack<int> input = new Stack<int>(); 
        for (int i = 0; i<n; i++) 
        input.Push(arr[i]); 
      
        // Sort the temporary stack 
        Stack<int> tmpStack = sortStack(input); 
      
        // Put stack elements in arrp[] 
        for (int i = 0; i < n; i++) 
        { 
            arr[i] = tmpStack.Peek(); 
            tmpStack.Pop(); 
        } 
    } 
      
    // Driver Code 
    static void Main() 
    { 
        int []arr = new int[] {10, 5,  
                               15, 45}; 
        int n = arr.Length; 
      
        sortArrayUsingStacks(arr, n); 
      
        for (int i = 0; i < n; i++) 
        Console.Write(arr[i] + " "); 
    } 
} 
  
// This code is contributed by  
// Manish Shaw(manishshaw1) 

Output:

5 10 15 45

Time Complexity : O(n*n)

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

C++

Java

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books