الترتيب السريع
الترتيب السريع من أكثر خوارزميات الترتيب استخدامًا. يختار محورًا، ويقسم القائمة إلى القيم الأصغر من المحور والباقي، ثم يرتب الجانبين بالطريقة نفسها. وهو سريع عمليًا ولا يحتاج إلى قائمة إضافية، لكن سرعته تعتمد على المحور.
الفكرة
اختر قيمة واحدة لتكون المحور. أعد ترتيب القائمة بحيث تأتي كل قيمة أصغر من المحور قبله وكل قيمة أخرى بعده. تُسمى إعادة الترتيب هذه تقسيمًا، وهي تترك المحور في الموضع الذي ينتمي إليه بالضبط في القائمة المرتبة. صار الجانبان الآن مسألتين مستقلتين: رتّب كلًّا منهما بالترتيب السريع. والجانب الذي فيه قيمة واحدة أو لا شيء مرتب أصلًا.
التقسيم خطوة بخطوة
يستخدم التطبيق تقسيم Lomuto. يُنقل المحور إلى نهاية الجزء. تبدأ علامة من البداية: كل ما قبلها أصغر من المحور. تُقارن كل قيمة أخرى بالمحور؛ فإن كانت أصغر تُبدَّل إلى موضع العلامة وتتقدم العلامة موضعًا واحدًا. وفي النهاية يُبدَّل المحور إلى موضع العلامة. خذ 5, 1, 4, 2, 8 مع القيمة الأخيرة محورًا: القيم الأربع كلها أصغر من 8، لذا تبقى 8 في النهاية. ثم يُقسَّم الجزء 5, 1, 4, 2 حول 2، فينتج 1, 2, 4, 5، ثم 4, 5 حول 5. أي 8 مقارنات و2 تبديل و3 تقسيمات.
المحاور الجيدة والسيئة
لو وقع كل محور في المنتصف، لقسم كل تقسيم المسألة إلى نصفين، واحتاج الترتيب إلى نحو n log₂ n مقارنة. في قائمة عشوائية نادرًا ما تكون المحاور مثالية، لكنها عادةً جيدة بما يكفي: لـ40 قيمة عشوائية يعدّ التطبيق نحو 190 مقارنة. وتأتي أسوأ حالة عندما يكون المحور دائمًا أصغر قيمة أو أكبرها. عند اختيار القيمة الأخيرة محورًا، هذا بالضبط ما يحدث مع قائمة مرتبة مسبقًا أو معكوسة: لا يُزيل كل تقسيم سوى المحور نفسه، ويحتاج الترتيب إلى n(n − 1)/2 مقارنة، أي 780 لـ40 قيمة.
اختيار المحور
يجعل المحور العشوائي أسوأ حالة مستبعدة جدًا لأي مدخلات، لأنه لا يوجد ترتيب بعينه يمكنه خداعه. ووسيط الثلاثة، أي القيمة الوسطى بين العنصر الأول والأوسط والأخير، رخيص الحساب ويتعامل جيدًا مع القوائم المرتبة والمعكوسة. جرّب الطريقتين على قائمة مرتبة في التطبيق، وستنخفض المقارنات من 780 إلى نحو 150. أما كثرة القيم المتساوية فمشكلة مختلفة: إذ تقع كلها في جانب واحد من المحور. والتقسيم الثلاثي، الذي يجمع القيم المساوية للمحور في جزء أوسط، يحل ذلك.
التاريخ والاستخدام
ابتكر Tony Hoare الترتيب السريع عام 1959 ونشره عام 1961. يمسح تقسيمه الأصلي من الطرفين ويجري تبديلات أقل؛ أما نسخة Lomuto الأبسط المعروضة هنا فقد انتشرت عبر الكتب الدراسية. يرتب الترتيب السريع في المكان، وحلقته الداخلية قصيرة جدًا، لذا يكون عادةً أسرع من الترتيب بالدمج عمليًا، رغم أنه غير مستقر. أما introsort، خوارزمية الترتيب في المكتبة القياسية لـC++، فتشغّل الترتيب السريع وتنتقل إلى الترتيب بالكومة إذا صارت التقسيمات غير متوازنة أكثر من اللازم، فتبقى أسوأ حالاتها n log n.
استكشفه
افتح التطبيق واضغط خطوة. يكون الجزء قيد التقسيم مظللًا، وللمحور لونه الخاص، ويحدد الخط المتقطع نهاية الجزء الأول، أي القيم الأصغر من المحور. ويتحول كل محور إلى اللون الأخضر عندما يصل إلى مكانه النهائي. اختر قائمة مرتبة والقيمة الأخيرة محورًا، ثم انتقل إلى وسيط الثلاثة، وقارن العدادات.
الأسئلة المتداولة
ما التعقيد الزمني للترتيب السريع؟
O(n log n) في المتوسط ومع المحاور الجيدة، وO(n²) في أسوأ حالة. يرتب في المكان؛ ويحتاج الاستدعاء الذاتي إلى ذاكرة إضافية O(log n) عند ترتيب الجانب الأصغر أولًا.
ما الفرق بين تقسيم Lomuto وتقسيم Hoare؟
يحتفظ Lomuto بعلامة واحدة ويمسح من البداية إلى النهاية، وهو سهل المتابعة وهو ما يعرضه هذا التطبيق. أما Hoare فيمسح من الطرفين باتجاه أحدهما الآخر ويبدّل الأزواج الموجودة في الجانب الخطأ، فيجري في المتوسط تبديلات أقل بنحو ثلاث مرات.
لماذا يكون الترتيب السريع بطيئًا عندما تتساوى قيم كثيرة؟
تذهب كل القيم المساوية للمحور إلى الجانب نفسه، لذا تنقسم القائمة ذات القيم المختلفة القليلة بشكل غير متوازن، وتكون قائمة القيم المتساوية سيئة كأسوأ حالة. والتقسيم الثلاثي الذي يجمع القيم المساوية للمحور في الوسط يتجنب ذلك.
هل الترتيب السريع مستقر؟
لا. التبديلات أثناء التقسيم تنقل القيم عبر مسافات طويلة، لذا قد يتغير ترتيب القيم المتساوية.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب الترتيب السريع