خوارزمية الترتيب الفقاعى Bubble Sorting

من أنواع خوارزميات الترتيب الفقاعي او bubble sorting هي خوارزمية سهلة الكتابة وكود بسيط، وتعتبر اول خوارزمية ترتيب يتم تعليمها للمبتدئين، ويقال انها من اسوء الخوارزميات للفرز والترتيب؛ الا اذا تم التحقق من ترتيب المصفوفة في كل تكرار ، ولمعرفة سبب هذا تابع القراءة.

كيف تعمل خوارزمية الترتيب الفقاعى؟

داخل حلقة التكرار يتم التحقق اذا كان العنصر الحالي ( i ) اكبر من العنصر التالي ( i+1 ) يتم التبديل بينهم ، وهذا بنقل كل منهما الي موقع الاخر.

في محرر بايثون بالاعلي تجد حلقة تكرار رئيسية، وحلقة فرعية. الحلقة الرئيسية هي تكرار عكسي يبدا من نهاية المصفوفة وينتهي في بدايتها، والحلقة الفرعية تكرر في نطاق الرقم الموجود في متغير حلقة التكرار الرئيسية.

لاحظ ان كل تكرار في الحلقة الرئيسية يجعل التكرار في الحلقة الفرعية اقل برقم واحد ويجب ان يكون اكبر عنصر موجود في نهاية نطاق التكرار الفرعي.

مثال التكرار الاول

7
[2, 19, 31, 45, 6, 11, 121, 27]
[2, 19, 31, 45, 6, 11, 121, 27]
[2, 19, 31, 45, 6, 11, 121, 27]
[2, 19, 31, 6, 45, 11, 121, 27]
[2, 19, 31, 6, 11, 45, 121, 27]
[2, 19, 31, 6, 11, 45, 121, 27]
[2, 19, 31, 6, 11, 45, 27, 121]

كما تلاحظ تم التكرار من الفهرس 0 الي الفهرس 7 في حلقة التكرار الفرعية، في اول تكرار 2 ليس اكبر من 19 لذلك لم يتم تغير شىء ، والتكرار الثاني 19 ليس اكبر من 31 لذلك لم يتغير شىء ايضاً ، وهذا حتي التكرار الرابع وهو 45 اكبر من 6 وهذا صحيح لذلك تم تبديل موقع العنصرين وتم الانتقال للتكرار التالي.

في التكرار التالي في الحلقة الفرعية 11 ليس اكبر من 45 و 45 ليس اكبر من 121 حتي اخر تكرار 121 اكبر من 27 لذلك تم التبديل بينهم وانتهي اول تكرار في الحلقة الرئيسية.

لاحظ ان اخر عنصر في المصفوفة وتحديداً رقم 7 لن يتم فحصة مرة اخري في عمليات التكرار التالية لان التكرار سوف ينتهي قبل الوصول اليه.

مثال علي باقي عمليات التكرار

6
[2, 19, 31, 6, 11, 45, 27, 121]
[2, 19, 31, 6, 11, 45, 27, 121]
[2, 19, 6, 31, 11, 45, 27, 121]
[2, 19, 6, 11, 31, 45, 27, 121]
[2, 19, 6, 11, 31, 45, 27, 121]
[2, 19, 6, 11, 31, 27, 45, 121]
5
[2, 19, 6, 11, 31, 27, 45, 121]
[2, 6, 19, 11, 31, 27, 45, 121]
[2, 6, 11, 19, 31, 27, 45, 121]
[2, 6, 11, 19, 31, 27, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]

حتي هنا تم ترتيب المصفوفة بالكامل، ولكن الخوارزمية لم تتوقف، ومازالت تتحقق من ترتيب العناصر، وهذا ما يعيب خوارزمية الترتيب الفقاعي bubble sort، ولحل تلك المشكلة؛ يمكن التحقق بعد انتهاء كل حلقة فرعية من ان المصفوفة تم ترتيبها بالكامل ام لا.

متابعة حلقة التكرار

4
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
3
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
2
[2, 6, 11, 19, 27, 31, 45, 121]
[2, 6, 11, 19, 27, 31, 45, 121]
1
[2, 6, 11, 19, 27, 31, 45, 121]