ما معنى Comparison Sort (الفرز بالمقارنة) في الخوارزميات وهياكل البيانات؟
الفرز بالمقارنة (Comparison Sort) هو أي خوارزمية ترتيب تُقرّر موضع العناصر اعتمادًا فقط على مقارنة عنصرين معًا في كل خطوة، بسؤال بسيط: أيهما أكبر؟ أيهما أصغر؟ أم أنهما متساويان؟ الخوارزمية لا تنظر إلى «قيمة» العنصر نفسه ولا تحسبها، بل تكتفي بنتيجة المقارنة (< أو > أو =) لتبني الترتيب النهائي. هذا التعريف يشمل معظم خوارزميات الفرز الشهيرة التي تصادفها: الفرز الفقاعي، والإدراج، والاختيار، والدمج (Merge Sort)، والفرز السريع (Quick Sort).
المفتاح الذي يغيب عن أغلب الشروحات المبسطة هو أن هذه العائلة من الخوارزميات تخضع لـحدّ نظري لا يمكن تجاوزه: لا توجد خوارزمية فرز بالمقارنة تستطيع ترتيب n عنصرًا بأسرع من O(n log n) مقارنة في الحالة العامة. فهم هذا الحدّ هو جوهر السؤال، وهو ما سنشرحه بلغة واضحة.
كيف تعمل خوارزمية الفرز بالمقارنة؟
الفكرة كلها تقوم على عملية واحدة متكررة: خُذ عنصرين، قارنهما، ثم اتخذ قرارًا (تبديل، إدراج، اختيار…) بناءً على النتيجة. يتكرر هذا آلاف أو ملايين المرات حتى تصبح القائمة مرتبة.
مثال عملي بسيط على مصفوفة [3, 1, 2] باستخدام فكرة الإدراج:
- نبدأ بالعنصر الأول
3ونعتبره مرتبًا. - نأخذ
1، نقارنه بـ3:1 < 3، فنُدرجه قبله ←[1, 3]. - نأخذ
2، نقارنه بـ3: أصغر، ثم بـ1: أكبر، فنضعه بينهما ←[1, 2, 3].
لاحظ أننا لم نحتج معرفة أن الأرقام «أرقام» أصلًا؛ لو كانت كلمات أو تواريخ أو أسماء لكان الأمر نفسه، ما دام لدينا طريقة لمقارنة أي عنصرين. هذه المرونة هي أعظم ميزة في الفرز بالمقارنة: يصلح لأي نوع بيانات تستطيع تعريف علاقة ترتيب له.
لماذا لا يمكن أن يكون أسرع من n log n؟
هذه هي النقطة التي تُميّز الفهم السطحي عن العميق. تخيّل أن كل مقارنة تعطيك إجابة من احتمالين (أكبر أو أصغر)، أي «بت» واحد من المعلومات. لترتيب n عنصرًا، عدد الترتيبات المحتملة هو n! (مضروب n). الخوارزمية يجب أن تُميّز بين كل هذه الاحتمالات لتصل إلى الترتيب الصحيح الوحيد.
ولأن كل مقارنة تُقلّص الاحتمالات إلى النصف في أفضل الأحوال، فأنت تحتاج على الأقل إلى log₂(n!) مقارنة. وبتقريب رياضي معروف (متسلسلة ستيرلينغ) فإن log₂(n!) يساوي تقريبًا n log n. لذلك مستحيل رياضيًا أن تنزل أي خوارزمية فرز بالمقارنة تحت هذا الحدّ في الحالة العامة. هذا ليس نقص براعة من المبرمجين، بل قانون رياضي.
أشهر خوارزميات الفرز بالمقارنة
| الخوارزمية | متوسط الأداء | الأسوأ | مستقرة؟ | متى تناسب |
|---|---|---|---|---|
| الفقاعي (Bubble) | O(n²) | O(n²) | نعم | للتعليم فقط |
| الاختيار (Selection) | O(n²) | O(n²) | لا | قوائم صغيرة جدًا |
| الإدراج (Insertion) | O(n²) | O(n²) | نعم | بيانات صغيرة أو شبه مرتّبة |
| الدمج (Merge) | O(n log n) | O(n log n) | نعم | بيانات كبيرة، أداء ثابت |
| السريع (Quick) | O(n log n) | O(n²) | لا | الأسرع عمليًا في الغالب |
نصيحة من واقع التطبيق: خوارزمية الفرز السريع (Quick Sort) هي الأسرع عمليًا في أغلب الحالات رغم أن حالتها الأسوأ O(n²)، لأن ثابتها الحسابي صغير وتستغل الذاكرة المؤقتة (cache) بكفاءة. أما الدمج (Merge Sort) فيقدّم ضمانًا ثابتًا بـ O(n log n) دائمًا لكنه يحتاج ذاكرة إضافية.
الفرز بالمقارنة مقابل الفرز بدون مقارنة
قد تتساءل: إذا كان n log n حدًّا صارمًا، فكيف نسمع عن خوارزميات ترتيب بسرعة O(n)؟ الجواب أنها ليست خوارزميات مقارنة. خوارزميات مثل Counting Sort و Radix Sort و Bucket Sort لا تقارن العناصر ببعضها، بل تستغل بنية البيانات نفسها (مثل كونها أعدادًا صحيحة ضمن مدى معروف) لتوزيعها مباشرة في «صناديق». لأنها تتجاوز خطوة المقارنة كليًا، فهي غير محكومة بحدّ n log n.
لكن لها ثمنًا: تعمل فقط على أنواع بيانات محددة (غالبًا أعداد صحيحة أو مفاتيح قصيرة)، وتحتاج ذاكرة إضافية، وتفقد المرونة العامة للفرز بالمقارنة. القاعدة العملية: إذا كنت تعرف طبيعة بياناتك بدقة ومداها محدود، فكّر في الفرز بدون مقارنة؛ وإلا فالفرز بالمقارنة هو الخيار الآمن والعام.
الأسئلة الشائعة
هل الفرز الفقاعي خوارزمية مقارنة؟ نعم، وهو من أوضح الأمثلة عليها، لأنه يعتمد كليًا على مقارنة كل زوج متجاور وتبديلهما عند الحاجة.
ما أسرع خوارزمية فرز بالمقارنة؟
لا توجد «أسرع» مطلقة؛ جميعها محكومة بـ O(n log n). لكن عمليًا يُعدّ الفرز السريع (Quick Sort) الأسرع في المتوسط، بينما يقدّم الدمج ضمانًا ثابتًا في أسوأ الحالات.
لماذا نتعلم خوارزميات بطيئة مثل الفقاعي إن كانت O(n²)؟
لأنها تشرح المبادئ الأساسية للمقارنة والتبديل بوضوح، وتُستخدم كأساس تعليمي قبل الانتقال إلى خوارزميات O(n log n) الأكثر تعقيدًا.
هل Radix Sort أفضل دائمًا لأنه O(n)؟ لا. يعمل فقط على بيانات ذات بنية محددة (كالأعداد الصحيحة)، ويستهلك ذاكرة إضافية، وقد يكون أبطأ فعليًا على بيانات صغيرة رغم تعقيده النظري الأفضل. تحقّق من طبيعة بياناتك أولًا.