Сортирајте стог користећи привремени стог


Ниво тешкоће Средњи
Често питани у амазонка Голдман Сакс ИБМ- Кулиза иахоо
сортирање Стацк

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

Проблем „Разврставање снопа помоћу привременог снопа“ наводи да сте добили а стек структура података. Разврстајте елементе датог стека помоћу привременог слога.

Сортирајте стог користећи привремени стог

Пример

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

На пример

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

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]

Како је стек празан, а привремени стек сортиран, одштампајте привремени стек почев од врха.

Према томе, излаз: 20 9 6 4 2 -1

Алгоритам за сортирање слога помоћу привременог слога

  1. Иницијализујте структуру података стека и уметните / потисните елементе у њој.
  2. Након тога креирајте функцију сорт () која прихваћа стек као свој параметар. Иницијализујте још један привремени / помоћни стек тмпСтацк у њему.
  3. Пређите док оригинални стек није празан, креирајте променљиву тмп и у њега сместите врх оригиналног стека. После тога ставите врх оригиналне хрпе.
  4. Опет пређите док тмпСтацк није празан и врх тмпСтацк-а, тј. Привремени стек је већи не мањи или једнак променљивој тмп, гурните врх привременог стека у оригинални стек и померите врх привременог стека.
  5. Гурните променљиву тмп у привремени стек.
  6. Иако привремени сноп није празан, одштампајте га на врху и отворите на врху.

код

Ц ++ програм за сортирање стека помоћу рекурзије

#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

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

Сложеност времена

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

Сложеност простора

Он) јер смо користили привремени простор за стек за н елемената. Простор који користи оригинални стог не рачуна се за алгоритам.