شرح خوارزمية Bubble Sort في Java مع الكود وتحسين الأداء

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

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

المثال التالي برنامج مستقل يقرأ مصفوفة أعداد، يرتبها تصاعديًا، ثم يطبع الناتج. انسخه في ملف BubbleSort.java وشغله من بيئة تطوير Java أو باستخدام javac وjava:

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] numbers) {
        int n = numbers.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] values = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(values);
        System.out.println(Arrays.toString(values));
    }
}

الناتج هو [11, 12, 22, 25, 34, 64, 90]. استخدمنا مصفوفة int، ودالة bubbleSort تستقبلها وتعدل ترتيب عناصرها مباشرة. المتغير i يحسب عدد مرات المرور، أما j فيتحرك داخل الجزء الذي لم يتم ترتيبه بعد. يقل الحد الداخلي بمقدار i لأن آخر i عناصر أصبحت في مكانها الصحيح.

في بداية المثال تقارن الخوارزمية 64 و34 فتبدلهما، ثم تقارن 64 و25 وتبدلهما، وتواصل العمل حتى تستقر القيمة 90 في النهاية. في المرور الثاني لا حاجة لمقارنة العنصر الأخير مرة أخرى؛ فهو أكبر قيمة وقد وصل إلى موضعه. تستمر العملية حتى يصبح الجزء غير المرتب صغيرًا، وتكون كل العناصر مرتبة تصاعديًا.

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

public static void optimizedBubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

يبلغ التعقيد الزمني المعتاد O(n²)، لأن هناك حلقتين متداخلتين، ويكون استخدام الذاكرة الإضافية O(1) لأن التبديل يتم داخل المصفوفة نفسها. في النسخة المحسنة تكون الحالة الأفضل O(n) عندما تكون البيانات مرتبة. هذه الخوارزمية مفيدة لفهم الحلقات والمقارنة والتبديل، لكنها ليست الاختيار المناسب للمصفوفات الكبيرة؛ فكفاءة Arrays.sort في الاستخدام العملي أفضل عادة.

لترتيب الأعداد من الأكبر إلى الأصغر، غير الشرط من numbers[j] > numbers[j + 1] إلى numbers[j] < numbers[j + 1]. عندها ستنتقل القيم الأصغر إلى نهاية المصفوفة مع كل مرور. اختبر الدالة أيضًا بمصفوفة فارغة، وبعنصر واحد، وبعناصر مكررة، وبقيم سالبة لتتأكد من صحة الحل في الحالات المختلفة.

لا، لأن عدد المقارنات يزداد بسرعة مع حجم البيانات. استخدمها للتعلم أو مجموعات صغيرة، واستخدم أدوات Java القياسية في التطبيقات الفعلية.

نعم، هذا المثال يرتب المصفوفة نفسها في مكانها ولا ينشئ نسخة جديدة.

للتعمق في الخوارزميات، اقرأ أيضًا مقالات Java التعليمية وتدرّب على مقارنة Bubble Sort بخوارزميات الترتيب الأخرى، ثم راجع درس الرسم في Java للتوسع في موضوعات لغة جافا.