ما معنى Partition في الخوارزميات وهياكل البيانات؟ شرح مبسّط مع أمثلة
كلمة Partition تعني ببساطة "التقسيم": أخذ مجموعة من العناصر وإعادة ترتيبها إلى قسمين (أو أكثر) وفق معيار محدد. لكن الكلمة تحمل أكثر من معنى في علوم الحاسوب، وأشهرها على الإطلاق هو خطوة التقسيم داخل خوارزمية الفرز السريع Quicksort: تختار عنصراً محورياً (Pivot)، ثم تعيد ترتيب العناصر بحيث يصبح كل ما هو أصغر منه على اليسار وكل ما هو أكبر على اليمين، فيستقرّ المحور في موضعه النهائي الصحيح. هذا هو المعنى الذي يبحث عنه أغلب الطلاب والمبرمجين عند كتابة هذا السؤال.
قبل الدخول في التفاصيل، من المهم التمييز بين معانٍ متعددة تشترك في نفس الكلمة، لأن الخلط بينها شائع جداً.
المعاني المختلفة لكلمة Partition
- خطوة التقسيم في الخوارزميات: كما في Quicksort وخوارزمية Quickselect لإيجاد العنصر رقم k. هذا هو موضوع المقال الأساسي.
- مسألة التقسيم (Partition Problem): مسألة رياضية تسأل هل يمكن تقسيم مجموعة أرقام إلى مجموعتين متساويتَي المجموع. وهي من المسائل الصعبة حسابياً (NP-complete).
- تقسيم البيانات (Data Partitioning / Sharding): توزيع صفوف جدول ضخم على خوادم أو أقراص متعددة في قواعد البيانات والأنظمة الموزّعة، لتسريع الاستعلامات.
- تقسيم القرص (Disk Partition): مفهوم عتاد لا علاقة له بالخوارزميات إطلاقاً، بل بتقسيم مساحة التخزين في نظام التشغيل.
المقال يركّز على المعنى الأول لأنه الأكثر بحثاً، مع لمحة عن الباقي.
كيف تعمل خطوة Partition في الفرز السريع
فكرة Quicksort أنها تعتمد على التقسيم بالكامل، ثم تكرر نفسها على كل قسم. الخطوات العملية:
- اختيار المحور (Pivot): عنصر من المصفوفة، غالباً الأخير أو الأول أو عنصر عشوائي.
- المرور على العناصر: قارن كل عنصر بالمحور.
- إعادة الترتيب: انقل كل عنصر أصغر من المحور إلى الجهة اليسرى عبر التبديل (Swap).
- وضع المحور في مكانه: بدّل المحور مع أول عنصر أكبر منه، فيستقرّ في موضعه النهائي.
- إرجاع فهرس التقسيم: الموضع الذي استقرّ فيه المحور، وهو ما يفصل القسمين.
- التكرار (Recursion): طبّق نفس العملية على القسم الأيسر ثم الأيمن حتى يصبح كل قسم بحجم عنصر واحد.
نقطة مهمة يخطئ فيها كثير من الشروحات: الفرز السريع لا يحتوي على خطوة "دمج" (Merge). الدمج موجود في خوارزمية الفرز بالدمج Merge Sort. أما Quicksort فيرتّب العناصر في مكانها (in-place) عبر التقسيم فقط، ولا يعيد تجميع الأجزاء لاحقاً.
Lomuto أم Hoare؟ أشهر طريقتين للتقسيم
هناك أسلوبان معروفان لتنفيذ خطوة التقسيم، ولكل منهما مزايا:
| المعيار | تقسيم Lomuto | تقسيم Hoare |
|---|---|---|
| اختيار المحور | عادةً العنصر الأخير | عادةً العنصر الأول أو الأوسط |
| آلية العمل | مؤشر واحد يتقدّم | مؤشران من الطرفين نحو المنتصف |
| عدد عمليات التبديل | أكثر | أقل (أكفأ عملياً) |
| سهولة الفهم | أبسط للمبتدئين | أعقد قليلاً |
| موضع المحور بعد التقسيم | يستقرّ نهائياً | لا يستقرّ بالضرورة |
للتعلّم والفهم، ابدأ بأسلوب Lomuto لوضوحه. أما في الأنظمة الحقيقية فأسلوب Hoare أسرع لأنه ينفّذ عمليات تبديل أقل.
Quickselect: تطبيق آخر مهم للتقسيم
نفس خطوة التقسيم تُستخدم في خوارزمية Quickselect لإيجاد العنصر رقم k (مثل الوسيط أو أكبر خمسة عناصر) دون الحاجة لفرز المصفوفة كاملة. بعد كل عملية تقسيم تعرف في أي نصف يقع العنصر المطلوب، فتتجاهل النصف الآخر. متوسط تعقيدها الزمني O(n) وهو أسرع من الفرز الكامل الذي يكلّف O(n log n).
التعقيد الزمني: لماذا يهم اختيار المحور؟
- الحالة المتوسطة: O(n log n)، وهي ممتازة وتجعل Quicksort من أسرع خوارزميات الفرز عملياً.
- الحالة الأسوأ: O(n²)، وتحدث عندما يكون المحور دائماً أصغر أو أكبر عنصر (مثلاً مصفوفة مرتّبة مسبقاً مع اختيار العنصر الأخير محوراً).
الحل العملي والخطأ الشائع: كثيرون يختارون المحور دائماً كأول أو آخر عنصر، فيقعون في الحالة الأسوأ مع البيانات المرتّبة. الأفضل اختيار محور عشوائي أو استخدام أسلوب "وسيط الثلاثة" (Median of Three) لتجنّب هذا الفخّ.
ملاحظة حول هياكل البيانات
في هياكل البيانات مثل شجرة البحث الثنائية (Binary Search Tree)، لا توجد خطوة "Partition" بالاسم، لكن الفكرة نفسها حاضرة: كل عقدة تقسّم القيم إلى فرع أيسر يحوي الأصغر وفرع أيمن يحوي الأكبر. لهذا يوصف مبدأ عملها أحياناً بأنه تقسيم لمجال القيم. أما في الأنظمة الموزّعة فالتقسيم يعني توزيع البيانات على عدة عُقد لتحقيق التوسّع الأفقي.
الأسئلة الشائعة
هل Partition خوارزمية مستقلة أم خطوة داخل خوارزمية؟ هي خطوة (إجراء فرعي) وليست خوارزمية كاملة. تصبح مفيدة عندما تُستخدم داخل Quicksort أو Quickselect.
ما الفرق بين Partition والفرز؟ التقسيم يرتّب العناصر حول محور واحد فقط (أصغر يساراً، أكبر يميناً) دون فرزها بالكامل. الفرز الكامل يتحقق بتكرار التقسيم على كل قسم.
هل الفرز السريع مستقر (Stable)؟ لا، الفرز السريع في صورته المعتادة غير مستقر، أي قد يغيّر الترتيب النسبي للعناصر المتساوية. إن كان الاستقرار مهماً فاستخدم Merge Sort.
متى أستخدم Quicksort ومتى أتجنّبه؟ استخدمه للبيانات العشوائية في الذاكرة حيث يتفوّق في السرعة. تجنّبه أو عدّل اختيار المحور مع البيانات المرتّبة مسبقاً، وتجنّبه إن كنت تحتاج ضمان O(n log n) في الحالة الأسوأ.