🎯 ترتيب الدمج

📖 نظرة عامة

⚙️ كيف يعمل ترتيب الدمج

عملية الدمج

خطوات خوارزمية الدمج

1. نسخ المصفوفتين الفرعيتين إلى مصفوفة مساعدة
2. مقارنة العناصر من كل مصفوفة فرعية
3. اختيار العنصر الأصغر ووضعه في النتيجة
4. تكرار حتى يتم دمج جميع العناصر

💻 التنفيذ بلغة جافا

دالة الدمج

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // نسخ العناصر إلى المصفوفة المساعدة
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];
    
    // الدمج مرة أخرى إلى المصفوفة الأصلية
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];  // الجزء الأيسر نفد
        else if (j > hi)               a[k] = aux[i++];  // الجزء الأيمن نفد
        else if (less(aux[j], aux[i])) a[k] = aux[j++];  // الجزء الأيمن أصغر
        else                            a[k] = aux[i++];  // الجزء الأيسر أصغر أو مساوي
    }
}

ترتيب الدمج من الأعلى للأسفل

public class Merge {
    private static void merge(...) { /* كما بالأعلى */ }
    
    private static void sort(Comparable[] a, Comparable[] aux, 
                                   int lo, int hi) {
        if (hi <= lo) return;                // الحالة الأساسية
        
        int mid = lo + (hi - lo) / 2;      // إيجاد المنتصف
        
        sort(a, aux, lo, mid);                // ترتيب النصف الأيسر
        sort(a, aux, mid + 1, hi);            // ترتيب النصف الأيمن
        merge(a, aux, lo, mid, hi);           // دمج النتائج
    }
    
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

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

لماذا O(N log N)؟

التحليل التجريبي

🔄 ترتيب الدمج من الأسفل للأعلى

الخوارزمية

1. مرّر المصفوفة، وادمج المصفوفات الفرعية بحجم 1
2. كرّر للمصفوفات الفرعية بحجم 2، 4، 8، 16، ...
3. استمر حتى يتم ترتيب المصفوفة بالكامل

التنفيذ

public static void sort(Comparable[] a) {
    int N = a.length;
    Comparable[] aux = new Comparable[N];
    
    // sz: حجم المصفوفات الفرعية للدمج (1, 2, 4, 8, ...)
    for (int sz = 1; sz < N; sz = sz + sz) {
        // lo: بداية المصفوفة الفرعية اليسرى
        for (int lo = 0; lo < N - sz; lo += sz + sz) {
            merge(a, aux, lo, lo + sz - 1, 
                  Math.min(lo + sz + sz - 1, N - 1));
        }
    }
}

⚖️ الاستقرار

لماذا يهم الاستقرار؟

مثال: سجلات الطلاب

هل ترتيب الدمج مستقر؟

if (less(aux[j], aux[i])) a[k] = aux[j++];
else                      a[k] = aux[i++];  // تأخذ من اليسار إذا تساوت

مقارنة الاستقرار

🔧 المقارنات

Comparable مقابل Comparator

مثال: مقارنات الطلاب

public class Student {
    private final String name;
    private final int section;
    
    // مقارن للترتيب حسب الاسم
    public static class ByName implements Comparator<Student> {
        public int compare(Student v, Student w) {
            return v.name.compareTo(w.name);
        }
    }
    
    // مقارن للترتيب حسب القسم
    public static class BySection implements Comparator<Student> {
        public int compare(Student v, Student w) {
            return v.section - w.section;
        }
    }
}

// الاستخدام:
Arrays.sort(students, new Student.ByName());
Arrays.sort(students, new Student.BySection());

ترتيبات النصوص الشائعة

📝 الملخّص والمقارنة

مقارنة خوارزميات الترتيب