ما هي خوارزمية Dual-Pivot Quicksort؟ شرح مبسّط لكيفية عملها ولماذا تتفوّق
خوارزمية Dual-Pivot Quicksort (الترتيب السريع بمحورين) هي نسخة مطوّرة من خوارزمية Quicksort المعروفة، لكنها تستخدم محورين اثنين بدل محور واحد، فتقسّم المصفوفة في كل خطوة إلى ثلاثة أقسام بدل قسمين. طوّرها المهندس فلاديمير ياروسلافسكي (Vladimir Yaroslavskiy) عام 2009، وأهميتها العملية أنها صارت منذ إصدار Java 7 هي الخوارزمية الافتراضية لترتيب المصفوفات الرقمية (مثل int وlong وdouble) داخل الدالة Arrays.sort. أي أنك غالبًا استخدمتها آلاف المرات دون أن تدري.
الفكرة الجوهرية: نختار محورين P1 ≤ P2، ثم نوزّع بقية العناصر إلى ثلاث فئات: أصغر من P1، وبين P1 وP2، وأكبر من P2. هذا التقسيم الثلاثي يقلّل عدد عمليات التبديل ويستغل ذاكرة المعالج المؤقتة (الكاش) بشكل أفضل، وهذا هو السبب الحقيقي لسرعتها العملية، كما سنوضّح.
كيف تعمل Quicksort الكلاسيكية أولًا
قبل المحورين، لنتذكّر الأصل بسرعة. Quicksort خوارزمية «فرّق تَسُد»: تختار عنصرًا واحدًا محورًا (pivot)، ثم تعيد ترتيب المصفوفة بحيث يصبح كل ما هو أصغر منه على يساره وكل ما هو أكبر على يمينه. بعد هذه الخطوة يستقر المحور في مكانه النهائي، وتُكرَّر العملية على القسمين يمينًا ويسارًا حتى تُرتَّب المصفوفة بالكامل.
ما الذي يضيفه المحوران؟
بدل تقسيم واحد ينتج قسمين، نستخدم محورين فينتج ثلاثة أقسام. تخيّل مصفوفة والمحوران هما P1 = 5 وP2 = 12:
- القسم الأول: كل ما هو أصغر من 5.
- القسم الأوسط: كل ما هو بين 5 و12.
- القسم الثالث: كل ما هو أكبر من 12.
بعد المرور مرّة واحدة على العناصر، يستقر المحوران في موضعيهما الصحيحين، ونعيد الكرّة على الأقسام الثلاثة. المكسب أنّ كل مرور واحد ينجز عملًا أكثر مقارنةً بالمحور الواحد.
خطوات الخوارزمية عمليًا
- اختر محورين وتأكّد أن
P1 ≤ P2(إن لزم بادِل بينهما). - استخدم مؤشرات تمسح المصفوفة من الطرفين نحو الوسط.
- ضع كل عنصر في قسمه: أصغر من
P1، أو بين المحورين، أو أكبر منP2. - ثبّت المحورين في موضعيهما النهائيين بعد انتهاء المسح.
- كرّر العملية بشكل تكراري (recursion) على كل قسم من الأقسام الثلاثة حتى يصبح حجم القسم صغيرًا جدًا، فتُنجزه خوارزمية بسيطة مثل الترتيب بالإدراج (insertion sort).
هل هي «أسرع» فعلًا؟ الحقيقة الدقيقة
هنا يقع خطأ شائع تكرّره كثير من الشروحات. الواقع أنّ زمن التنفيذ في المتوسط يبقى O(n log n) تمامًا كـ Quicksort العادية، والحالة الأسوأ تبقى O(n²) إن سوءت أُختِير المحوران، فالمحوران لا يلغيان هذا الاحتمال.
أما من ناحية العدّ الفعلي، فقد أظهرت أبحاث سيباستيان فيلد وماركوس نيبل أنّ نسخة ياروسلافسكي تُجري في المتوسط مقارنات أقل قليلًا (نحو 1.9 n ln n مقابل 2 n ln n) لكنها تُجري عمليات تبديل أكثر (نحو 0.6 n ln n مقابل 0.33 n ln n). فمن أين تأتي السرعة إذن؟ من أنماط الوصول إلى الذاكرة: طريقة المسح المتتابع تلائم ذاكرة الكاش في المعالجات الحديثة، فتقلّ حالات الفشل في الوصول (cache misses). هذا هو التفسير الأدق، وليس مجرد «تقليل المقارنات».
Quicksort الكلاسيكية أم Dual-Pivot؟
| الخاصية | Quicksort (محور واحد) | Dual-Pivot Quicksort |
|---|---|---|
| عدد المحاور | واحد | اثنان |
| الأقسام لكل خطوة | قسمان | ثلاثة أقسام |
| الزمن في المتوسط | O(n log n) | O(n log n) |
| الحالة الأسوأ | O(n²) | O(n²) |
| المقارنات (تقريبًا) | ~2 n ln n | ~1.9 n ln n |
| عمليات التبديل (تقريبًا) | ~0.33 n ln n | ~0.6 n ln n |
| مستقرة (stable)؟ | لا | لا |
| أبرز استخدام | تعليمي وعام | افتراضية للأرقام في Java |
أين تلتقي بها فعليًا؟
أشهر تطبيق عملي هو مكتبة Java القياسية. عند استدعاء Arrays.sort على مصفوفة أرقام أولية، تعمل نسخة محسّنة من هذه الخوارزمية خلف الكواليس: تختار عدة عناصر كعيّنة (خمسة عناصر في التطبيق الكلاسيكي) وتستعمل اثنين منها كمحورين لتحسين جودة الاختيار، وتلجأ إلى الترتيب بالإدراج للمصفوفات الصغيرة. لاحظ أنّ Java لا تستخدمها لترتيب مصفوفات الكائنات (Objects)، بل تستخدم TimSort لأنها مستقرة بينما الترتيب السريع ليس كذلك. وتختلف التفاصيل الدقيقة بين إصدارات JDK، لذا اعتبر ما سبق وصفًا للمبدأ لا للشيفرة الحرفية.
نصيحة عملية: إن كنت تكتب مشروعًا حقيقيًا، لا تعيد كتابة هذه الخوارزمية بنفسك؛ استعمل دالة الترتيب الجاهزة في لغتك فهي مختبَرة ومحسّنة. أعِد تنفيذها يدويًا فقط بهدف الفهم أو في مقابلات العمل.
الأسئلة الشائعة
هل Dual-Pivot Quicksort أسرع دائمًا من العادية؟ لا. هي أسرع في المتوسط عمليًا على الأجهزة الحديثة بسبب استغلال الكاش، لكن الحالة الأسوأ تبقى O(n²)، وقد تتفوّق العادية في حالات خاصة.
هل هي خوارزمية مستقرة (stable)؟ لا. قد تتغيّر المواضع النسبية للعناصر المتساوية، ولهذا تُستخدم TimSort حين تكون الاستقرارية مطلوبة.
هل يمكن استخدام ثلاثة محاور أو أكثر؟ نعم بحثيًا جُرِّبت نسخ بثلاثة محاور، لكن المكاسب تتضاءل بينما يزداد تعقيد الشيفرة، فلم تصبح الخيار الافتراضي.
هل تعمل في المكان (in-place)؟ نعم، لا تحتاج ذاكرة إضافية تُذكر عدا مساحة المكدّس للاستدعاءات التكرارية بحدود O(log n).