Сортирај меур со користење на два Купишта


Ниво на тешкотија Лесно
Често прашувано во Амазон Капгемини Деливерија MAQ
Низа Сортирање

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

Проблемот „Сортирање меур со употреба на две стакови“ вели дека ви е даден низа a [] со големина n. Создадете функција за сортирање на дадената низа a [] со помош на парадигма за сортирање меурчиња со две структури на податоци за стек.

Сортирај меур со користење на два Купишта

пример

a[ ] = {15, 12, 44, 2, 5, 10}
2 5 10 12 15 44
a[ ] = {5, 6, 4, 2, 3, 1}
1 2 3 4 5 6

Алгоритам

  1. Иницијализира ан низа a [] со големина n.
  2. Создадете ја функцијата за Сортирај дадената низа a [] користејќи сортирање меурчиња парадигма со двајца магацинот структури на податоци кои прифаќаат низа и нивната големина е параметар.
  3. Создадете структура на податоци за стек на број тип Поминете низ дадената низа и турнете ги сите елементи на низата во оџакот.
  4. Слично на тоа, креирајте друга структура на податоци за стек од цел број тип.
  5. После тоа, поминете низ 0 до n-1. Проверете дали тековниот индекс МО 2 е еднаков на 0, преминете повторно додека првиот оџак не е празен.
  6. Создадете цел број променлива и попувајте го елементот на горниот дел од првиот оџак и зачувајте го.
  7. Проверете дали вториот оџак е празен, притиснете / вметнете ја целобројната променлива во вториот оџак. Друго проверете дали елементот на горниот дел од втората магацинот е поголем од целобројната променлива, креирајте привремена променлива, попувајте го елементот на горниот дел од вториот стек и зачувајте го во привремената променлива. Притиснете ја целосната променлива во вториот оџак. После тоа, турнете ја привремената променлива во вториот оџак.
  8. Друго, ако елементот на горниот дел од вториот оџак е помал или еднаков на целобројната променлива, турнете ја променливата цел број во оџакот.
  9. Појавете го горниот дел од вториот оџак и зачувајте го во низата a [] со индекс n-1-тековен индекс.
  10. Друго ако тековниот индекс МО 2 е еднаква на 0, поминувајте додека вториот оџак не е празен.
  11. Создадете целобројна променлива и попувајте го елементот на горниот дел од вториот оџак и зачувајте го во него.
  12. Проверете дали првиот оџак е празен, притиснете / вметнете ја целобројната променлива во првиот оџак. Друго проверете дали елементот на горниот дел од првиот оџак е поголем од целобројната променлива, создадете привремена променлива, попувајте го елементот на горниот дел од првиот оџак и зачувајте го во привремената променлива. Притиснете ја целосната променлива во првиот оџак. После тоа, турнете ја привремената променлива во првиот оџак.
  13. Друго, ако елементот на врвот на првиот оџак е помал или еднаков на целобројната променлива, турнете ја променливата цел број во оџакот.
  14. Појавете го горниот дел од првиот оџак и зачувајте го во низата a [] со индекс n-1-тековен индекс.
  15. Печатете ја сортираната низа.

Код

Програма C ++ за спроведување на сортирање на меурчиња со користење на два Купишта

#include <bits/stdc++.h>
using namespace std;

void bubbleSortStack(int a[], int n){ 
    stack<int> s1;
      
    for(int i = 0; i < n; i++){ 
        s1.push(a[i]);
    }
      
    stack<int> s2;
      
    for(int i = 0; i < n; i++){ 
        
        if(i % 2 == 0){ 
            while (!s1.empty()){ 
                int t = s1.top();
                s1.pop(); 
                  
                if(s2.empty()){ 
                    s2.push(t);  
                }
                
                else{ 
                    
                    if(s2.top() > t){ 
                        int temp = s2.top(); 
                        s2.pop(); 
                        s2.push(t); 
                        s2.push(temp); 
                    } 
                    
                    else{ 
                        s2.push(t); 
                    } 
                } 
            } 
            a[n-1-i] = s2.top();
            s2.pop(); 
        }     
        
        else{
            
            while(!s2.empty()){ 
                int t = s2.top();
                s2.pop();
                  
                if (s1.empty()){ 
                    s1.push(t); 
                }
                  
                else{ 
                    
                    if (s1.top() > t){ 
                        int temp = s1.top();
                        s1.pop(); 
                          
                        s1.push(t); 
                        s1.push(temp); 
                    } 
                    
                    else{
                        s1.push(t); 
                    }
                } 
            } 
              
            a[n-1-i] = s1.top();
            s1.pop(); 
        } 
    }
    
    for(int i = 0; i < n; i++){
        cout<< a[i] << " "; 
    }
} 
  
int main() {
  int a[] = {15, 12, 44, 2, 5, 10};
  int n = sizeof(a)/sizeof(a[0]);
    
  bubbleSortStack(a, n); 
    
  return 0;
}
2 5 10 12 15 44

Јава програма за спроведување на сортирање меурчиња со користење на два Купишта

import java.util.Arrays; 
import java.util.Stack; 
  
class Sort{ 
    
    static void bubbleSortStack(int a[], int n){ 
        Stack<Integer> s1 = new Stack<>(); 
          
        for(int num : a){ 
            s1.push(num);
        }
          
        Stack<Integer> s2 = new Stack<>(); 
          
        for(int i = 0; i < n; i++){ 
            
            if(i % 2 == 0){ 
                while (!s1.isEmpty()){ 
                    int t = s1.pop(); 
                      
                    if(s2.isEmpty()){ 
                        s2.push(t);  
                    }
                    
                    else{ 
                        
                        if(s2.peek() > t){ 
                            int temp = s2.pop(); 
                            s2.push(t); 
                            s2.push(temp); 
                        } 
                        
                        else{ 
                            s2.push(t); 
                        } 
                    } 
                } 
                a[n-1-i] = s2.pop(); 
            }     
            
            else{
                
                while(!s2.isEmpty()){ 
                    int t = s2.pop(); 
                      
                    if (s1.isEmpty()){ 
                        s1.push(t); 
                    }
                      
                    else{ 
                        
                        if (s1.peek() > t){ 
                            int temp = s1.pop(); 
                              
                            s1.push(t); 
                            s1.push(temp); 
                        } 
                        
                        else{
                            s1.push(t); 
                        }
                    } 
                } 
                  
                a[n-1-i] = s1.pop(); 
            } 
        }
        
        for(int i = 0; i < n; i++){
            System.out.print(a[i]+" "); 
        }
    } 
      
    public static void main(String[] args){
        
        int a[] = {15, 12, 44, 2, 5, 10};
        
        bubbleSortStack(a, a.length); 
    } 
}
2 5 10 12 15 44

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

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

О (n ^ 2) каде n е бројот на цели броеви во дадената низа a []. Ова е вообичаена сложеност во времето што ја бара Подредување на меурчиња.

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

Тој) затоа што користевме простор за n елементи. Ова складирање е потребно за купишта.