ما معنى exchange sort: see bubble sort؟ شرح الفرز بالتبادل وعلاقته بفرز الفقاعة
إذا صادفتك عبارة exchange sort: see bubble sort أثناء بحثك، فهي ليست اسمًا لخوارزمية غامضة، بل مجرد إحالة قاموسية. النقطتان وكلمة "see" تعنيان حرفيًا: «الفرز بالتبادل: انظر فرز الفقاعة». هذه الصيغة مأخوذة من قواميس المصطلحات البرمجية الشهيرة مثل قاموس الخوارزميات وهياكل البيانات الصادر عن المعهد الأمريكي NIST، حيث يُحيلك المصطلح الأول إلى تعريفه الأساسي تحت اسم آخر. باختصار: Exchange Sort في هذا السياق هو نفسه Bubble Sort (فرز الفقاعة)، وما تبحث عنه فعليًا هو فهم كيفية عمل فرز الفقاعة.
لكن هناك تفصيلًا مهمًا يغفله كثيرون، وسأوضحه بعد شرح الأساس حتى لا تقع في خلط شائع.
ما هو فرز الفقاعة (Bubble Sort) بالضبط؟
فرز الفقاعة خوارزمية ترتيب تعمل بمنطق بسيط: قارن كل عنصرين متجاورين، وبدّلهما إن كانا في الترتيب الخاطئ، وكرّر المرور على القائمة حتى تصبح مرتّبة. سُمّيت "فقاعة" لأن أكبر قيمة تطفو تدريجيًا نحو نهاية القائمة في كل مرور، تمامًا كفقاعة الهواء التي تصعد إلى سطح الماء.
كلمة "Exchange" (تبادل) تصف جوهر العملية: الترتيب يحدث عبر تبديل مواضع العناصر، لا عبر نقلها أو إدراجها. لهذا وُضع المصطلحان كمترادفين في القواميس.
كيف يعمل خطوة بخطوة
لنأخذ القائمة [5, 3, 8, 4, 2] ونرتّبها تصاعديًا:
- قارن 5 و3: 5 أكبر، بدّلهما ←
[3, 5, 8, 4, 2] - قارن 5 و8: بالترتيب الصحيح، لا تبديل.
- قارن 8 و4: بدّلهما ←
[3, 5, 4, 8, 2] - قارن 8 و2: بدّلهما ←
[3, 5, 2, 4, 8]
بهذا اكتمل المرور الأول، ووصل الرقم 8 (الأكبر) إلى مكانه الصحيح في النهاية. نكرّر المرور على العناصر المتبقية، ومع كل جولة يستقر عنصر جديد في موضعه، حتى تُرتَّب القائمة بالكامل: [2, 3, 4, 5, 8].
نصيحة عملية غالبًا ما تُنسى: أضف متغيّرًا منطقيًا (flag) يتتبّع ما إذا حدث أي تبديل خلال المرور. إذا مررتَ على القائمة كاملة دون تبديل واحد، فهي مرتّبة أصلًا، فتوقّف فورًا. هذا التحسين البسيط يجعل الخوارزمية تنتهي بزمن O(n) عند إعطائها قائمة شبه مرتّبة، بدلًا من إهدار جولات لا لزوم لها.
الأداء: لماذا لا يُنصح بها للبيانات الكبيرة؟
في أسوأ الحالات وفي الحالة المتوسطة، زمن تنفيذ فرز الفقاعة هو O(n²)، أي أن مضاعفة حجم البيانات تُربّع تقريبًا عدد العمليات. لذلك تصبح بطيئة جدًا مع آلاف العناصر. لكنها في المقابل:
- مستقرة (Stable): تحافظ على الترتيب النسبي للعناصر المتساوية.
- تعمل في المكان (In-place): لا تحتاج ذاكرة إضافية تُذكر (O(1)).
- سهلة الفهم والكتابة: لهذا تُدرَّس أولًا في مساقات الخوارزميات.
مقارنة سريعة مع خوارزميات الترتيب الأخرى
| الخوارزمية | الحالة المتوسطة | الذاكرة الإضافية | مستقرة؟ | الأنسب لـ |
|---|---|---|---|---|
| فرز الفقاعة (Bubble/Exchange) | O(n²) | O(1) | نعم | التعليم وقوائم صغيرة جدًا |
| فرز الإدراج (Insertion) | O(n²) | O(1) | نعم | قوائم صغيرة أو شبه مرتّبة |
| الفرز السريع (Quick Sort) | O(n log n) | O(log n) | لا | البيانات الكبيرة عمومًا |
| الفرز بالدمج (Merge Sort) | O(n log n) | O(n) | نعم | عندما يهم الاستقرار والحجم كبير |
القاعدة العملية: استخدم فرز الفقاعة للتعلّم وللقوائم الصغيرة فقط، وانتقل إلى Quick Sort أو Merge Sort للبيانات الحقيقية الكبيرة. وفي معظم لغات البرمجة الحديثة، الأفضل ببساطة استدعاء دالة الترتيب المدمجة (مثل sort()) التي تعتمد خوارزميات هجينة مُحسّنة.
الخلط الشائع الذي يجب تجنّبه
انتبه: مصطلح "Exchange Sort" يُستخدم أحيانًا في مراجع أخرى للإشارة إلى خوارزمية مختلفة قليلًا تقارن كل عنصر بكل العناصر التي تليه (وليس المجاور فقط). لذلك حين ترى "exchange sort: see bubble sort" تحديدًا، فالمقصود هو فرز الفقاعة بمعناه الكلاسيكي. اعتمد دائمًا على السياق والمصدر، ولا تفترض أن الاسم وحده يحدّد آلية العمل.
الأسئلة الشائعة
هل exchange sort و bubble sort شيء واحد؟ في سياق العبارة "see bubble sort" نعم، هما اسمان لنفس الفكرة القائمة على تبديل العناصر المتجاورة. لكن بعض المصادر تفرّق بينهما، لذا تحقّق من تعريف المصدر الذي تقرأه.
لماذا كُتبت بصيغة "see bubble sort"؟ لأنها إحالة قاموسية تنقلك من المصطلح إلى تعريفه الرئيسي، تمامًا كما يفعل أي معجم حين يقول «انظر المدخل الآخر».
ما تعقيد فرز الفقاعة الزمني؟ O(n²) في الحالتين المتوسطة والأسوأ، وO(n) في أفضل حالة إذا استخدمت تحسين متغيّر التبديل مع قائمة مرتّبة مسبقًا.
متى أستخدمه في مشروع حقيقي؟ نادرًا. اختره فقط حين تكون البيانات صغيرة جدًا أو حين تريد توضيح الفكرة تعليميًا. لأي عمل جدّي استخدم دالة الترتيب المدمجة في لغتك أو خوارزمية بزمن O(n log n).