خوارزمية الترتيب الفقاعي | Bubble Sort Algorithm

خوارزمية الترتيب الفقاعي من خوارزميات الترتيب الأساسية، و هذا بكل تأكيد لا يخفي عليك كدارس لعلوم الخوارزميات. لماذا سميت بخوارزميات الترتيب الفقاعي و كيف تعمل مع إستعراض مثال شارح و عرض الشفرة الخاصة بها ستكون هذه محطات في تدوينتي لهذا اليوم.

سُميت خوارزمية الترتيب الفقاعي بهذا الإسم لسبب لطيف. فكما تأخذ الفقاعة طريقها لتعلو خارج الماء فإن العناصر في هذه الخوارزمية تأخذ طريقها لمكانها الصحيح بطريقة تشبه الفقاعة، و ستشاهد هذا في المثال.

‍

طريقة عمل خوارزمية الترتيب الفقاعي

حتى تعرف كيف تعمل الخوارزمية سأوضح لك الفكرة العامة أو المفهوم الأساسي لخوارزمية الترتيب الفقاعي، يجب أن تركز على هذه الخطوات، ثم مستصحباً هذه الفكرة سيرسخ لك المثال خوارزمية الترتيب الفقاعي أيما ترسيخ.

1. الفكرة الاساسية لخوارزمية الترتيب الفقاعي هي أن تضع أكبر عنصر في المصفوفة في مكانه الصحيح في كل دورة.
2. ماذا يحدث في كل دورة؟ تضع المؤشر في أول عنصر بالمصفوفة، ثم تقارنه مع العُنصر التالي:
   1. إذا كان العنصر الأول أصغر من العنصر الثاني، أنقل المؤشر إلى العنصر التالي (لا يوجد تبديل).
   2. إذا كان العنصر الأول أكبر من العنصر الثاني، بدل العنصر الثاني مع العنصر الأول ثم أنقل المؤشر إلى العنصر التالي (يوجد تبديل).
   3. نواصل العملية حتى العنصر قبل الأخير بالمصفوفة.
3. عدد عناصر المصفوفة التي ترتبها خوارزمية الترتيب الفقاعي في كل دورة تقل بواحد حتى تنتهي العناصر، فإذا كان عدد عناصر المصفوفة 5، ففي الدورة الثانية ستُرتب 4 و الدورة الثالثة ستُرتب 3 عناصر و هكذا. لماذا؟ لأنه في كل دورة تضع الخوارزمية عنصراً في مكانه الصحيح، فبالتالي لا نحتاج لإدخاله في عملية الترتيب مرة أخرى.
4. عدد الدورات = عدد عناصر المصفوفة – 1، لماذا؟ حاول تخيلها… حسناً، في أول دورةنأخذ العناصر كاملة، و يقل عدد العناصر بواحد كلما إنتقلنا إلى دورة التالية و هكذا حتى نصل إلى أن يكون عدد العناصر المتبقية 2. هنا.. إذا كانت العناصر مرتبة فقد إكتمل الترتيب، و إذا لم تكن مرتبة فسترتبها و إكتمل الترتيب، أليس كذلك؟ إذاً فما فائدة ترتيب العنصر الأخير لوحده؟ لهذا تجد أن عدد الدورات في خوارزمية الترتيب الفقاعي = عدد العناصر – 1.
5. إذا ما كانت المصفوفة مرتبة أصلاً، و أجريت عليها خوارزمية الترتيب الفقاعي، كيف تعرف أن المصفوفة مرتبة مسبقاً؟ فكّر و تفكّر.. إذا ما وجدت أن الخوارزمية أكلمت دورة كاملة دون أن تجري عملية تغيير واحدة، عندها تعلم أن المصفوفة مرتبة (هذه قاعدة إنتبه لها).
6. في أي مرحلة إذا ما علمت أن مصفوفتك مرتبة فلا داعي لإكمال خوارزمية الترتيب الفقاعي، و ذلك بإستخدام القاعدة السابقة، فقد يكون العنصر الأول و الثاني فقط في غير موضعهم، و بإجراء أول عملية تبديل يكون قد إكتمل ترتيب المصفوفة. في الدورة التالية لن يحدث أي تبديل و بذلك تكون قد علمت أن المصفوفة مرتبة… أوقف الخوارزمية. كيف توقفها؟ هكذا تسأل؟ سترى بشفرة الجافا أدناه.

مثال لخوارزمية الترتيب الفقاعي

[tie_full_img][/tie_full_img]

هذه الصورة الشارحة لنفسها بنفسها إذا ما قرأت طريقة عمل الخوارزمية و نظرت إلى الصورة فستجد أنك قد ربطت جميع المفاهيم و علمت كيف تعمل خوارزمية الترتيب الفقاعي.

لكن على كُلٍ سأشرح لك الدورة الأولى من خوارزمية الترتيب كما تظهر بالصورة، و إذا ما اختلط عليك شئ ضعه بالتعليقات لأجيبك عليه بإذن الله.

الدورة الأولى من خوارزمية الترتيب الفقاعي

• وُضع المؤشر بالعنصر رقم 1، تمت مقارنته بالعنصر رقم 2. 5<12 إذا لا يوجد تغيير، نضع المؤشر على العنصر الثاني.
• 12>9، إذا في هذه الحالة وفقاً لمفاهيم الخوارزمية ماذا نفعل؟ نجري عملية تبديل، فيأخذ 12 مكان 9 و 9 تأخذ مكان 12، ننقل المؤشر إلى العنصر التالي. ركز جداً سيكون العنصر التالي هو الرقم 12. لماذا؟ لأن المؤشر إنتقل من العنصر رقم 2 إلى العنصر رقم 3، عملية التبديل ليس لها أي تأثير على مكان المؤشر فالمؤشر أعمى أبكم أصم. عندما يأتي دوره ينفذ ما عليه بالإنتقال إلى العنصر التالي دون أن يراعي ماذا جرى قبل أو بعد.
• 12>7، إذا نجري نفس العملية السابقة، تبديل بين 12 و 7، و ينتقل المؤشر إلى العنصر الرابع و هو 12.
  لأن العنصر رقم 12 هو أكبر عنصر بالمصفوفة فسيزيح جميع العناصر متقدماً مثل الفقاعة إلى أن يحتل مكانه الحقيق و هو آخر عنصر بالمصفوفة.

شفرة جافا لخوارزمية الترتيب الفقاعي

public static int[] bubblesort(int[] numbers) {
    boolean swapped = true;
    for(int i = numbers.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (numbers[j] > numbers[j+1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                swapped = true;
            }
        }
    }
    return numbers;
}

6 مفاهيم أساسية لخوارزمية الترتيب الفقاعي ضعها نصب عينيك في أي عملية ترتيب، هذه نصيحتي لك، إذا ما أفادتك هذه التدوينة شاركها مع أصدقائك ، و يسعدني تعليقك أدناه جداً، كما يمكنك الاطلاع علي التدوينات التالية في نفس المجال.

شرح خوارزمية الترتيب بالإدخال [سطر سطر]

خوارزمية الترتيب بالإختيار: الشرح السهل مع التنفيذ