اقرأ في هذا المقال
- ما هي خوارزمية الترتيب بالفقاعات؟
- كيف تعمل خوارزمية الترتيب بالفقاعات؟
- تعقيدات الوقت لخوارزمية الترتيب بالفقاعات
- تطبيقات خوارزمية الترتيب بالفقاعات
ما هي خوارزمية الترتيب بالفقاعات؟
خوارزمية الترتيب بالفقاعات وهي خوارزمية ترتيب بسيطة، تعد خوارزمية الترتيب هذه خوارزمية قائمة على المقارنة، حيث تقوم الخوارزمية فيها بمقارنة كل زوج من العناصر المتجاورة، وتقوم تبديل العناصر إذا لم تكن بالترتيب المقصود، يمكن أن يكون الترتيب تصاعدياً أو تنازلياً، هذه الخوارزمية غير مناسبة لمجموعات البيانات الكبيرة؛ وذلك لأن تعقيد الوقت لهذه الخوارزمية في الحالة المتوسطة وأسوأ حالة لها هي “Ο(n²)”، حيث (n) هي عدد العناصر.
تُعرف الخوارزمية باسم ترتيب بالفقاعات؛ وذلك لأنه مع كل تكرار كامل، فإن أكبر عنصر في المصفوفة المعطاة، يتجه نحو أخر مكان في المصفوفة أو أعلى مؤشر (index)، تمامًا مثل ارتفاع فقاعة الماء إلى سطح الماء.
كيف تعمل خوارزمية الترتيب بالفقاعات؟
1- على سبيل المثال، لنأخذ مصفوفة لمجموعة من الأعداد الغير مرتبة، بدءًا من الفهرس (index) الأول، تقوم الخوارزمية بمقارنة العنصر الأول بالعنصر الثاني، فإذا كان العنصر الأول أكبر من العنصر الثاني، فيتم تبديلهما، ثم تقارن بين العنصر الثاني والعنصر الثالث، وتقوم بتبديلهما إذا لم يكونا بالترتيب التصاعدي، تستمر العملية المذكورة أعلاه حتى العنصر الأخير.
2- تستمر نفس العملية للتكرارات المتبقية، بعد كل تكرار، تقوم الخوارزمية بوضع أكبر عنصر بين العناصر غير المرتبة في النهاية، وفي كل تكرار، وتقوم الخوارزمية بالمقارنة حتى آخر عنصر لم يتم ترتيبه، يتم ترتيب المصفوفة عند وضع جميع العناصر غير المرتبة في مواضعها الصحيحة.
تعقيدات الوقت لخوارزمية الترتيب بالفقاعات:
أسوأ حالة تعقيد: “O(n²)”، وتحدث إذا أردنا ترتيب المصفوفة بالترتيب التصاعدي وكانت المصفوفة بالترتيب التنازلي، فإن أسوأ حالة تحدث.
أفضل حالة تعقيد: “O(n)”، وتحدث إذا كانت المصفوفة مرتبة بالفعل، فلا حاجة للترتيب.
متوسط حالة تعقيد: “O(n²)”، وتحدث إذا كانت عناصر المصفوفة في ترتيب مختلط (لا تصاعدي ولا تنازلي).
تطبيقات خوارزمية الترتيب بالفقاعات:
تستخدم خوارزمية الترتيب بالفقاعات في الحالات التالية حيث:
- تستخدم خوارزمية الترتيب بالفقاعات بشكل أساسي للأغراض التعليمية لمساعدة الطلاب على فهم أُسس الترتيب.
- وتستخدم الخوارزمية أيضاً، إذا لم يكن تعقيد الوقت مهماً في الكود.
- وإذا كان المُبرمج يفضل استخدام كود قصير.
