مجموعة الفرز باستخدام الأكوام  


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

بيان المشكلة  

تشير مشكلة "فرز المصفوفة باستخدام Stacks" إلى أنه تم منحك بنية بيانات مجموعة أ [] بحجم n. تصنيف حسب: عناصر المصفوفة باستخدام كومة هيكل البيانات.

مجموعة الفرز باستخدام الأكوامدبوس

مثال  

2 30 -5 43 100
-5 2 30 43 100

توضيح: تم فرز العناصر بترتيب تصاعدي.

2 3 1 8 6
1 2 3 6 8

نهج لفرز المصفوفة باستخدام الأكوام  

قم بإنشاء بنية بيانات مكدس لتخزين جميع عناصر مصفوفة الإدخال المحددة أ []. بعد ذلك ، قم بإنشاء مكدس مؤقت آخر لفرز المجموعة الأصلية. كرر خلال المكدس الأصلي ولكل عنصر انبثق من الأعلى وقم بتخزينه في متغير مؤقت. وبالمثل ، قم بالتكرار خلال المكدس المؤقت بينما يكون العنصر الموجود أعلى المكدس المؤقت أقل من القمة المنبثقة للمكدس الأصلي. أدخل العنصر العلوي للمكدس المؤقت في المكدس الأصلي وقم بإزالته من المكدس المؤقت. ادفع الجزء العلوي المنبثق للمكدس الأصلي في المكدس المؤقت. في النهاية ، ستحتوي الحزمة المؤقتة على عناصر مرتبة بترتيب. هذه المشكلة هي تعديل طفيف على الفرز أ كومة باستخدام مكدس مؤقت.

خوارزمية  

  1. تهيئة مصفوفة [] بحجم n.
  2. إنشاء بنية بيانات مكدس. اجتياز المصفوفة [] وادفع كل عناصر المصفوفة [] في المكدس.
  3. وبالمثل ، قم بإنشاء مكدس مؤقت آخر.
  4. قم بالانتقال بينما لا يكون حجم المكدس الأصلي 0. ​​قم بإنشاء متغير tmp وقم بتخزين العنصر في أعلى المكدس الأصلي فيه وقم بإزالته من المكدس الأصلي.
  5. قم بالعبور مرة أخرى بينما لا يكون المكدس المؤقت فارغًا وقم ببث العنصر في أعلى المكدس المؤقت حتى يصبح أقل من المتغير tmp. أثناء الظهور من المكدس المؤقت ، ادفع العنصر العلوي للمكدس المؤقت في المكدس الأصلي.
  6. ادفع المتغير tmp في مكدس مؤقت.
  7. انتقل من 0 إلى n-1 وقم بتخزين العنصر العلوي للمكدس المؤقت في المصفوفة a [] في الفهرس الحالي وانبثق / احذف العنصر من المكدس المؤقت.
  8. أخيرًا ، انتقل من 0 إلى n-1 واطبع المصفوفة [].
انظر أيضا
أوجد أقصى مجموع ممكن لمجموع متساوي لثلاث مجموعات

رمز  

برنامج C ++ لفرز المصفوفة باستخدام Stacks

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(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; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}
-5 2 30 43 100

برنامج Java لفرز المصفوفة باستخدام Stacks

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}
-5 2 30 43 100

تحليل التعقيد  

تعقيد الوقت

O (ن ^ 2) حيث n هو عدد العناصر في المكدس. نظرًا لأننا نقوم بدفع العناصر للخلف من المكدس المؤقت إلى المكدس الأصلي في حالة كان الجزء العلوي من المكدس المؤقت أقل من العنصر المراد دفعه. لفهم أفضل ، ضع في اعتبارك تسلسل ترتيب تنازلي وحاول تشغيل الخوارزمية.

تعقيد الفضاء

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