47. القسِّم تسُد (Divide and Conquer): مراجعة Merge Sort و Quick Sort

لقد واجهنا بالفعل الأمثلة الأكثر أساسية لـ Divide and Conquer (D&C) في الفرز.

خصائص D&C

• الاستقلالية (Independence): يجب حل المشكلات الفرعية التي تم إنشاؤها أثناء مرحلة 'التقسيم' بشكل مستقل عن بعضها البعض. لا تؤثر حلولها على حلول المشكلات الفرعية الأخرى.
• الهيكل المتطابق: المشكلات الفرعية عادة ما تكون نُسخاً أصغر من المشكلة الرئيسية.

مثال: Merge Sort (D&C خالص)

1. التقسيم (Divide): تقسيم المصفوفة [1..N] إلى [1..N/2] و [N/2+1..N].
2. التغلب (Conquer): فرز النصفين بشكل عودي.
3. الجمع (Combine): دمج النصفين المفرزين.

مثال: Quick Sort (D&C مع التقسيم)

1. التقسيم (Divide): تقسيم المصفوفة حول المحور P.
2. التغلب (Conquer): فرز العناصر الموجودة على يسار P والعناصر الموجودة على يمين P بشكل عودي.
3. الجمع (Combine): لا توجد خطوة جمع صريحة مطلوبة، حيث يضمن التقسيم أن P موجود بالفعل في مكانه.