दुई स्ट्याक्सको प्रयोग गरेर बबल क्रमबद्ध गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Capgemini दिल्लीवरी MAQ
एरे क्रमबद्ध

समस्या वक्तव्य

समस्या "दुई स्ट्याकको प्रयोग गरेर बुलबुले क्रमबद्ध गर्नुहोस्" बताउँछ कि तपाईंलाई एक दिइएको छ array a [] आकार n को। दिईएको एर्रेलाई क्रमबद्ध गर्न प्रकार्य सिर्जना गर्नुहोस् [] दुई स्ट्याक डाटा स्ट्रक्चरको साथ बबल सॉर्ट प्याराडाइम प्रयोग गरेर।

दुई स्ट्याक्सको प्रयोग गरेर बबल क्रमबद्ध गर्नुहोस्

उदाहरणका

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. सुरु गर्नुहोस् array a [] आकार n को।
  2. प्रकार्य सिर्जना गर्नुहोस् भाग्य दिइएको एर्रे एक [] प्रयोग गर्दै बबल क्रमबद्ध दुई संग प्रतिमान स्ट्याक डाटा संरचना जसले एर्रे स्वीकार्छ र यसको आकार यो प्यारामिटरको रूपमा छ।
  3. को स्ट्याक डेटा संरचना सिर्जना गर्नुहोस् पूर्णांक प्रकार दिइएको एर्रे को माध्यम बाट पार गर्नुहोस् र एर्रेको सबै एलिमेन्टहरूलाई स्ट्याकमा धकेल्नुहोस्।
  4. त्यस्तै, पूर्णांक प्रकारको अर्को स्ट्याक डेटा संरचना सिर्जना गर्नुहोस्।
  5. त्यस पछि, ० बाट एन -१ सम्म पार गर्नुहोस्। जाँच गर्नुहोस् यदि हालको इन्डेक्स मोड २ बराबर ० छ, फेरि ट्र्याभर्स गर्नुहोस् जबकि पहिलो स्ट्याक खाली छैन।
  6. पूर्णांक भ्यारीएबल सिर्जना गर्नुहोस् र पहिलो स्ट्याकको शीर्षमा एलिमेन्ट पप गर्नुहोस् र यसलाई भण्डार गर्नुहोस्।
  7. दोस्रो स्ट्याक खाली छ कि छैन जाँच गर्नुहोस्, दोस्रो स्ट्याकमा पूर्णांक भ्यारीएबल / घुसाउनुहोस्। अर्को जाँच गर्नुहोस् कि यदि दोस्रो स्ट्याकको माथि एलिमेन्ट पूर्णांक भ्यारीएबल भन्दा ठूलो छ, अस्थायी भ्यारीएबल सिर्जना गर्नुहोस्, दोस्रो स्ट्याकको शीर्षमा एलिमेन्ट पप गर्नुहोस् र यसलाई अस्थायी भ्यारीएबलमा भण्डार गर्नुहोस्। दोस्रो स्ट्याकमा पूर्णांक भ्यारीएबल पुश गर्नुहोस्। त्यस पछि, दोस्रो स्ट्याकमा अस्थायी भ्यारीएबल पुश गर्नुहोस्।
  8. अन्यथा यदि दोस्रो स्ट्याकको शीर्षमा तत्व पूर्णांक भ्यारीएबल भन्दा कम वा बराबर छ भने, स्ट्याकमा पूर्णांक भ्यारीएबललाई धक्का दिनुहोस्।
  9. दोस्रो स्ट्याकको शीर्ष पप गर्नुहोस् र यो एर्रेमा भण्डार गर्नुहोस् [] सूचकांकमा एन-१-वर्तमान सूचकांकमा।
  10. अन्यथा यदि हालको अनुक्रमणिका विरुद्ध २ बराबर ० ० हुन्छ, ट्र्याभर्स जबकि दोस्रो स्ट्याक खाली हुँदैन।
  11. एक पूर्णांक चर बनाउनुहोस् र दोस्रो स्ट्याकको शीर्षमा एलिमेन्ट पप गर्नुहोस् र यसमा भण्डार गर्नुहोस्।
  12. चेक पहिलो स्ट्याक खाली छ, पहिलो स्ट्याकमा पूर्णांक भ्यारीएबल / घुसाउनुहोस्। अर्को जाँच गर्नुहोस् कि यदि पहिलो स्ट्याकको माथि एलिमेन्ट पूर्णांक भ्यारीएबल भन्दा ठूलो छ, एउटा अस्थायी भ्यारीएबल सिर्जना गर्नुहोस्, पहिलो स्ट्याकको शीर्षमा एलिमेन्ट पप गर्नुहोस् र यसलाई अस्थायी भ्यारीएबलमा भण्डार गर्नुहोस्। पहिलो स्ट्याकमा पूर्णांक भ्यारीएबल पुश गर्नुहोस्। त्यस पछि, पहिलो स्ट्याकमा अस्थायी भ्यारीएबल पुश गर्नुहोस्।
  13. अन्यथा यदि पहिलो स्ट्याकको शीर्षमा तत्व पूर्णांक भ्यारीएबल भन्दा कम वा बराबर छ भने, स्ट्याकमा पूर्णांक भ्यारीएबललाई थिच्नुहोस्।
  14. पहिलो स्ट्याकको शीर्ष पप गर्नुहोस् र एर्रे ए [] अनुक्रमणिका एन-१-वर्तमान सूचकांकमा भण्डार गर्नुहोस्।
  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

जटिलता विश्लेषण

समय जटिलता

O (n ^ 2) जहाँ n अ given्क दिइएको एरेमा पूर्णांकको संख्या हो []। यो सामान्य समय जटिलता हो बुलबुला क्रमबद्ध गर्न आवश्यक छ।

ठाउँ जटिलता

ऊ) किनभने हामीले n तत्वहरूका लागि ठाउँ प्रयोग गर्‍यौं। यो भण्डारण स्ट्याक्सको लागि आवश्यक छ।