24. فرز السريع (Quick Sort): التقسيم والعودية (الجزء 2)

مخطط Lomuto للتقسيم (مبسط)

1. اختر العنصر الأخير كمحور (pivot).
2. استخدم فهرساً i (يبدأ عند العنصر الأول) لتتبع المكان الذي ينتهي فيه الحد 'الأصغر'.
3. التكرار عبر المصفوفة باستخدام j:
   • إذا كان arr[j] أصغر من أو يساوي المحور، قم بتبديل arr[i] و arr[j]، وقم بزيادة i.
4. أخيراً، قم بتبديل المحور إلى الموضع i.

تحليل الكفاءة

• الوقت في الحالة المتوسطة: O(N log N). هذا فعال للغاية وعادة ما يكون أسرع عملياً من Merge Sort بسبب عوامل ثابتة أفضل (يستخدم عمليات وصول أقل للذاكرة Cache).
• الوقت في أسوأ حالة: O(N²).
  • يحدث هذا إذا كان اختيار المحور ضعيفاً باستمرار (على سبيل المثال، اختيار أصغر أو أكبر عنصر دائماً)، مما يؤدي إلى تقسيمات غير متوازنة (مصفوفة فرعية بحجم N-1 ومصفوفة بحجم 0). هذا نادر مع استراتيجيات اختيار المحور الجيدة (مثل وسيط الثلاثة أو المحور العشوائي).