Подредете оџак користејќи привремен оџак


Ниво на тешкотија Медиум
Често прашувано во Амазон Голдман Сакс IBM, Кулиза Јаху
Сортирање Магацинот

Изјава за проблем

Проблемот „Сортирај оџак користејќи привремен оџак“ наведува дека ти е дадена a магацинот структура на податоци. Подредете ги елементите на дадениот оџак користејќи привремен оџак.

Подредете оџак користејќи привремен оџак

пример

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

На пример

Нека Stack = [9 4 2 -1 6 20] и привремен Stack = []

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

Бидејќи Stack е празен и привремениот Stack е подреден, отпечатете го привремениот Stack почнувајќи од горе.

Затоа, Излез: 20 9 6 4 2 -1

Алгоритам за подредување на оџакот користејќи привремен оџак

  1. Иницијализирајте структура на податоци за стек и вметнете / турнете ги елементите во неа.
  2. После тоа, креирајте сортирање на функции () што прифаќа оџак како негов параметар. Иницијализирајте друг привремен / помошен стек tmpStack во него.
  3. Поминувајте додека оригиналниот оџак не е празен, создадете променлива tmp и зачувајте го горниот дел од оригиналниот оџак во него. После тоа, се појавува горниот дел од оригиналниот оџак.
  4. Повторно поминувајте додека tmpStack не е празен, а горниот дел од tmpStack, т.е. привремениот оџак е поголем не помалку од или еднаков на променливата tmp, притиснете го горниот дел од привремениот оџак во оригиналниот оџак и излезете го горниот дел од привремениот оџак.
  5. Притиснете ја променливата tmp во привремениот оџак.
  6. Додека привремениот оџак не е празен, отпечатете го горе и поп - горе.

Код

Програма C ++ за сортирање на оџак користејќи рекурзија

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(stack<int> &input){ 
    stack<int> tmpStack; 
  
    while(!input.empty()){ 
        
        int tmp = input.top(); 
        input.pop(); 
  
        while(!tmpStack.empty() && tmpStack.top() > tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

Јава програма за сортирање на оџакот користејќи рекурзија

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

Анализа на сложеност

Временска комплексност

О (n ^ 2) каде n е бројот на елементи во оџакот. Бидејќи ги туркаме елементите назад од привремениот оџак во оригиналниот оџак во случај горниот дел од привремениот оџак да биде помал од елементот што треба да се турка. За подобро разбирање, размислете за редоследот на опаѓачки редослед и обидете се да го извршите алгоритмот.

Комплексноста на просторот

Тој) затоа што користевме привремен простор за магацинот за n елементи. Просторот што го користи оригиналниот оџак не се смета за алгоритмот.