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