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)
leave a comment
0 Comments