Tutorialspoint.dev

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 


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)

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)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter