Сортиране на балончета с помощта на два стека


Ниво на трудност Лесно
Често задавани в Амазонка Capgemini Делхейвъри Maq
Array сортиране

Декларация за проблема

Проблемът „Bubble sort using two Stacks“ гласи, че сте получили масив 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-current index.
  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

Java програма за внедряване на сортиране на балончета с помощта на два стека

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

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

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

O (n ^ 2) където n е броят на целите числа в даден масив a []. Това е обичайната времева сложност, изисквана от Bubble Sort.

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

О (п) защото използвахме място за n елемента. Това съхранение е необходимо за стекове.