🚀 الترتيب السريع

1. المقدمة والتاريخ

القصة وراء الترتيب السريع

اخترع توني هور الترتيب السريع بقصة مثيرة للاهتمام:

• أنشأها في البداية لحل مشكلة ترجمة لكن لم يستطع شرحها أو تنفيذها
• تعلم Algol 60 ومفهوم التكرار
• نفّذ الترتيب السريع بنجاح باستخدام تقنيات التكرار
• نشر الخوارزمية في Communications of the ACM (يوليو 1961)

لماذا يهم الترتيب السريع

2. كيف يعمل الترتيب السريع

الخطة الأساسية

مثال مرئي

3. خوارزمية التقسيم

كيف يعمل التقسيم

خطوات التقسيم:

1. تهيئة المؤشرات: ضع i للإشارة مباشرة بعد أقصى اليسار، وj للإشارة إلى أقصى اليمين
2. المسح من اليسار: زيادة i حتى إيجاد عنصر ≥ المحور
3. المسح من اليمين: إنقاص j حتى إيجاد عنصر ≤ المحور
4. التبادل: تبادل العناصر في الموضعين i وj
5. التكرار: استمر في الخطوات 2-4 حتى يتقاطع المؤشران
6. التبادل النهائي: تبادل المحور مع العنصر في الموضع j

4. التنفيذ بلغة جافا

تنفيذ الترتيب السريع الكامل

public class Quick {
    
    // طريقة الترتيب الرئيسية
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);  // الخلط لضمان الأداء
        sort(a, 0, a.length - 1);
    }
    
    // طريقة الترتيب المتكررة
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);      // ترتيب المصفوفة الفرعية اليسرى
        sort(a, j+1, hi);      // ترتيب المصفوفة الفرعية اليمنى
    }
    
    // طريقة التقسيم
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        
        while (true) {
            // إيجاد عنصر على اليسار للتبادل
            while (less(a[++i], a[lo]))
                if (i == hi) break;
            
            // إيجاد عنصر على اليمين للتبادل
            while (less(a[lo], a[--j]))
                if (j == lo) break;
            
            // التحقق إذا تقاطع المؤشران
            if (i >= j) break;
            
            // التبادل
            exch(a, i, j);
        }
        
        // التبادل مع عنصر التقسيم
        exch(a, lo, j);
        
        // إرجاع فهرس العنصر المعروف الآن أنه في مكانه
        return j;
    }
    
    // طرق مساعدة
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

5. تحليل الأداء

التعقيد الزمني

التحليل الرياضي

أوقات التشغيل التجريبية

6. التعامل مع المفاتيح المكررة

مشكلة المفاتيح المكررة

مقارنة مرئية

7. الخصائص والمميزات

الترتيب في نفس المكان

الاستقرار

الأولي:  B₁ C₁ C₂ A₁
بعد:    A₁ B₁ C₂ C₁  ← تبادل ترتيب C₂ و C₁!

ملخص الخصائص

8. المقارنة مع خوارزميات الترتيب الأخرى

لماذا الترتيب السريع أسرع عمليًا

9. التطبيقات العملية وترتيبات النظام

ترتيب النظام في جافا

الخوارزميات المستخدمة:

أداء العالم الحقيقي: الدروس المستفادة

متى تستخدم الترتيب السريع

🎓 النقاط الرئيسية

📝 نصائح الدراسة