23. فرز السريع (Quick Sort): استراتيجية المحور (Pivot) (الجزء 1)
Quick Sort هي خوارزمية الفرز الأكثر استخداماً على نطاق واسع من الناحية العملية. مثل Merge Sort، تستخدم نموذج القسِّم تسُد (Divide and Conquer).
المفهوم: التقسيم (Partitioning)
مفتاح Quick Sort هو عملية التقسيم (Partition). وهي تعتمد على اختيار عنصر محوري (pivot) وإعادة ترتيب المصفوفة بحيث:
- تأتي جميع العناصر الأصغر من المحور قبله.
- تأتي جميع العناصر الأكبر من المحور بعده.
بعد التقسيم، يُضمن أن يكون العنصر المحوري في موضعه المفرز النهائي.
خطوات Quick Sort
- اختيار المحور (Pivot): حدد عنصراً (غالباً ما يكون الأخير أو عنصراً عشوائياً).
- التقسيم (Partition): أعد ترتيب المصفوفة حول المحور.
- العودية (Recurse): طبق Quick Sort بشكل عودي على المصفوفة الفرعية للعناصر الأقل من المحور والمصفوفة الفرعية للعناصر الأكبر من المحور.