ما هي خوارزمية Quicksort؟ شرح مبسّط لطريقة عملها وأدائها مع أمثلة

خوارزمية Quicksort (الترتيب السريع) هي خوارزمية لترتيب عناصر قائمة أو مصفوفة تصاعديًا أو تنازليًا، وتقوم على مبدأ «فرّق تَسُد» (Divide and Conquer): بدل ترتيب القائمة كاملةً دفعة واحدة، تختار عنصرًا مرجعيًا يُسمى المحور (Pivot)، ثم توزّع بقية العناصر حوله بحيث يستقر كل عنصر أصغر منه على يساره وكل عنصر أكبر منه على يمينه، وتكرّر العملية نفسها على كل جانب حتى تُرتَّب القائمة بالكامل. طوّرها العالم البريطاني توني هوار عام 1959، وما زالت حتى 2026 من أكثر خوارزميات الترتيب استخدامًا داخل المكتبات البرمجية لأنها سريعة وتعمل «في المكان» دون الحاجة إلى ذاكرة إضافية كبيرة.

كيف تعمل Quicksort خطوة بخطوة؟

الفكرة أبسط مما تبدو. لترتيب مصفوفة:

1. اختر المحور (Pivot): عنصرًا واحدًا من المصفوفة (أول عنصر، أو آخر عنصر، أو عنصرًا عشوائيًا).
2. قسّم (Partition): أعد ترتيب باقي العناصر بحيث تنتقل القيم الأصغر من المحور إلى يساره، والأكبر إلى يمينه. بعد هذه الخطوة يصبح المحور في موضعه النهائي الصحيح داخل المصفوفة المرتّبة.
3. كرّر (Recursion): طبّق الخطوتين نفسيهما على الجزء الأيسر (العناصر الأصغر) وعلى الجزء الأيمن (العناصر الأكبر) كلٍّ على حدة.
4. توقّف عندما يصبح كل جزء فرعي مكوّنًا من عنصر واحد أو صفر — فهو مرتّب تلقائيًا.

مثال عملي سريع

لِنرتّب المصفوفة [7, 2, 9, 3, 5]، وليكن المحور آخر عنصر وهو 5:

• نمرّ على العناصر: 2 و3 أصغر من 5 فيذهبان لليسار، بينما 7 و9 أكبر فيذهبان لليمين.
• تصبح المصفوفة: [2, 3, 5, 7, 9]، والمحور 5 استقر في مكانه الصحيح.
• نكرّر العملية على [2, 3] يسارًا وعلى [7, 9] يمينًا، فتُرتَّبان بسرعة، وتنتهي الخوارزمية.

في شيفرة Python يمكن تلخيص الفكرة (بنسخة تعليمية مبسّطة) هكذا:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left  = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x >  pivot]
    return quicksort(left) + [pivot] + quicksort(right)

ملاحظة مهمة: هذه النسخة سهلة للفهم لكنها تُنشئ قوائم جديدة وتستهلك ذاكرة إضافية؛ أما التطبيقات الحقيقية فتنفّذ التقسيم داخل المصفوفة نفسها (in-place) لتوفير الذاكرة.

ما مدى سرعة Quicksort؟ (التعقيد الزمني)

هنا تكمن النقطة التي يغفل عنها كثيرون: أداء Quicksort يعتمد بشدة على جودة اختيار المحور.

• الحالة المتوسطة: ‎O(n log n)‎ — وهي سريعة جدًا وسبب شهرتها.
• أفضل حالة: ‎O(n log n)‎ — حين يقسّم المحور القائمة إلى نصفين متساويين تقريبًا في كل مرة.
• أسوأ حالة: ‎O(n²)‎ — وتحدث عندما يكون المحور دائمًا أصغر أو أكبر عنصر، مثل ترتيب مصفوفة مرتّبة مسبقًا مع اختيار أول أو آخر عنصر كمحور ثابت.

الخطأ الشائع: استخدام أول أو آخر عنصر محورًا ثابتًا على بيانات شبه مرتّبة، فينهار الأداء إلى O(n²). الحل العملي هو اختيار محور عشوائي أو استخدام تقنية «وسيط الثلاثة» (Median-of-Three) التي تأخذ وسيط أول عنصر وأوسطه وآخره. أما استهلاك الذاكرة فهو O(log n) في المتوسط بسبب مكدّس الاستدعاء المتكرر.

نقطة أخرى تستحق الانتباه: Quicksort غير مستقرة (Not Stable)، أي قد تغيّر الترتيب النسبي للعناصر المتساوية القيمة. إن كان الحفاظ على هذا الترتيب مهمًا (كترتيب سجلات حسب حقلين)، ففكّر في Merge Sort بدلًا منها.

Quicksort أم Merge Sort؟

كلاهما يعمل بمبدأ «فرّق تَسُد»، لكنهما يختلفان في التفاصيل التي تحدّد الاختيار:

المعيار	Quicksort	Merge Sort
التعقيد في المتوسط	‎O(n log n)	‎O(n log n)
أسوأ حالة	‎O(n²)	‎O(n log n)
الذاكرة الإضافية	قليلة، ‎O(log n) (في المكان)	‎O(n) (تحتاج مصفوفة مساعدة)
الاستقرار	غير مستقرة	مستقرة
الأداء الفعلي	أسرع عمليًا غالبًا	ثابت ومضمون

الخلاصة العملية: Quicksort أسرع في المتوسط وأوفر للذاكرة، لذا تُفضَّل للبيانات العامة في الذاكرة. أما Merge Sort فيُختار حين تكون هناك حاجة لضمان O(n log n) دائمًا أو للحفاظ على الاستقرار، وكذلك في ترتيب الملفات الضخمة على القرص.

أين تُستخدم Quicksort عمليًا؟

كثير من المكتبات القياسية لا تستخدم Quicksort «خام» بل نسخة هجينة تُسمى Introsort، تبدأ بـ Quicksort ثم تتحوّل تلقائيًا إلى خوارزمية أخرى (مثل Heapsort) إذا لاحظت اقترابها من أسوأ حالة، وتلجأ إلى Insertion Sort للأجزاء الصغيرة جدًا. بهذا تجمع بين سرعة Quicksort وأمان O(n log n). لهذا حين تستدعي دالة ترتيب جاهزة في لغتك، فأنت غالبًا تستفيد من روح Quicksort دون أن تكتبها بنفسك.

الأسئلة الشائعة

هل Quicksort هي الأسرع دائمًا؟ لا. هي الأسرع في المتوسط لمعظم البيانات، لكنها قد تتدهور إلى O(n²) مع اختيار محور سيئ على بيانات مرتّبة مسبقًا. اختيار المحور العشوائي يعالج ذلك عمليًا.

لماذا تُسمى «الترتيب السريع» رغم أن أسوأ حالتها بطيئة؟ لأن أسوأ حالة نادرة الحدوث عند الاختيار الجيد للمحور، وفي التطبيق الفعلي تتفوق على أغلب الخوارزميات المنافسة بفضل عملها في المكان واستفادتها الجيدة من الذاكرة المؤقتة (Cache).

ما الفرق بين المحور (Pivot) والتقسيم (Partition)؟ المحور هو العنصر المرجعي الذي تقارن به، والتقسيم هو عملية إعادة ترتيب العناصر حول هذا المحور لتضع الأصغر يسارًا والأكبر يمينًا.

هل يجب أن أكتب Quicksort بنفسي في مشاريعي؟ غالبًا لا؛ استخدم دالة الترتيب الجاهزة في لغتك فهي مُحسَّنة ومختبَرة. تعلُّم Quicksort يبقى مهمًا لفهم المبادئ وللمقابلات التقنية وحل المشكلات الخاصة.