فرز الفقاعات باستخدام اثنين من الأكوام


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون كابجيميني التسليم MAQ
مجموعة فرز

المشكلة بيان

تنص مشكلة "فرز الفقاعات باستخدام مكدسين" على أنه تم منحك الامتداد مجموعة أ [] بحجم 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. تهيئة ملف مجموعة أ [] بحجم n.
  2. قم بإنشاء الوظيفة إلى sort المصفوفة المعطاة [] تستخدم فقاعة الفرز نموذج مع اثنين كومة هياكل البيانات التي تقبل المصفوفة وحجمها كمعامل.
  3. إنشاء بنية بيانات مكدس من عدد صحيح يكتب. اجتياز المصفوفة المحددة وادفع جميع عناصر المصفوفة في المكدس.
  4. وبالمثل ، قم بإنشاء بنية بيانات مكدس أخرى من نوع عدد صحيح.
  5. بعد ذلك ، انتقل من 0 إلى n-1. تحقق مما إذا كان تعديل الفهرس الحالي 2 يساوي 0 ، واجتياز مرة أخرى عندما لا يكون المكدس الأول فارغًا.
  6. قم بإنشاء متغير عدد صحيح وقم ببث العنصر في أعلى المجموعة الأولى وقم بتخزينه.
  7. تحقق مما إذا كانت المجموعة الثانية فارغة ، ادفع / أدخل متغير العدد الصحيح في المجموعة الثانية. تحقق أيضًا مما إذا كان العنصر الموجود أعلى المكدس الثاني أكبر من متغير العدد الصحيح ، وأنشئ متغيرًا مؤقتًا ، وقم بفك العنصر في أعلى المجموعة الثانية وقم بتخزينه في المتغير المؤقت. ادفع متغير العدد الصحيح في المجموعة الثانية. بعد ذلك ، ادفع المتغير المؤقت في المجموعة الثانية.
  8. وإلا إذا كان العنصر الموجود أعلى المكدس الثاني أقل من أو يساوي متغير العدد الصحيح ، فادفع متغير العدد الصحيح في المكدس.
  9. انبثق الجزء العلوي من المكدس الثاني وقم بتخزينه في المصفوفة [] في الفهرس n-1-current.
  10. وإلا إذا كان الفهرس الحالي وزارة الدفاع 2 يساوي 0 ، اجتياز بينما المكدس الثاني ليس فارغًا.
  11. قم بإنشاء متغير عدد صحيح وقم ببث العنصر في أعلى المجموعة الثانية وقم بتخزينه فيه.
  12. التحقق من أن المكدس الأول فارغ ، ادفع / أدخل متغير العدد الصحيح في الحزمة الأولى. تحقق أيضًا مما إذا كان العنصر الموجود في أعلى الحزمة الأولى أكبر من متغير العدد الصحيح ، وأنشئ متغيرًا مؤقتًا ، وقم بفك العنصر في الجزء العلوي من المجموعة الأولى وقم بتخزينه في المتغير المؤقت. ادفع متغير العدد الصحيح في المكدس الأول. بعد ذلك ، ادفع المتغير المؤقت في المجموعة الأولى.
  13. وإلا إذا كان العنصر الموجود أعلى المكدس الأول أقل من أو يساوي متغير العدد الصحيح ، فادفع متغير العدد الصحيح في المكدس.
  14. ضع الجزء العلوي من المكدس الأول وقم بتخزينه في المصفوفة [] في الفهرس n-1-current.
  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 (ن ^ 2) حيث n هو عدد الأعداد الصحيحة في مصفوفة معينة a []. هذا هو التعقيد الزمني المعتاد الذي تتطلبه Bubble Sort.

تعقيد الفضاء

O (ن) لأننا استخدمنا مساحة لعدد n من العناصر. هذا التخزين مطلوب للأكوام.