آشنایی با الگوریتم مرتب سازی حباب (با مثال در جاوا)

مرتب‌سازی حبابی ساده‌ترین الگوریتم مرتب‌سازی است. با مقایسه مکرر عناصر مجاور و تعویض آنها در صورت عدم ترتیب درست کار می کند. به عنوان مثال، اگر ترتیب مرتب سازی صعودی باشد، عناصر مجاور با هم مقایسه می شوند و عنصر بزرگتر در سمت راست قرار می گیرد. در هر تکرار، ما فقط عناصر مرتب نشده را با هم مقایسه می کنیم و بزرگترین عنصر در آخرین موقعیت عناصر مرتب نشده در آرایه قرار می گیرد.

این الگوریتم به درستی Bubble Sort نام دارد، زیرا عناصر در هر تکرار به سمت راست آرایه حرکت می کنند، دقیقاً مانند حباب های آب که به سطح می روند.

کار از مرتب سازی حباب

فرض کنید می خواهیم این آرایه را به ترتیب صعودی مرتب کنیم

تکرار اول

در اولین تکرار، سعی می کنیم بزرگترین عنصر را به انتهای آرایه منتقل کنیم. بنابراین، ما بارها و بارها عناصر مجاور را با هم مقایسه می کنیم و در صورت نامرتب بودن آنها را تعویض می کنیم.

گفته می شود عناصری که به موقعیت صحیح خود رفته اند مرتب شده اند.

تکرارهای بعدی

این فرآیند برای همه تکرارها تکرار می شود تا آرایه مرتب شود. در هر تکرار، ما فقط عناصر مرتب نشده را با هم مقایسه می کنیم، زیرا عناصر مرتب شده از قبل به ترتیب صحیح هستند.

ما از طریق آرایه تکرار می کنیم n-1 بار، که در آن n طول آرایه است. یعنی از آنجایی که آرایه ما شش عنصر دارد، فقط پنج بار در آرایه تکرار می کنیم. زیرا پس از تکرار پنجم، پنج عنصر در موقعیت صحیح خود قرار گرفته اند، بنابراین عنصر مرتب نشده نهایی مرتب شده در نظر گرفته می شود. پس از تمام تکرارها، یک آرایه مرتب شده خواهیم داشت.

پیاده سازی مرتب سازی حباب

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // loop through array size-1 times
        for (int i = 0; i < size - 1; i++) {
            // loop until end of unsorted elements
            for (int j = 0; j < size - i - 1; j++) {
                // swap left and right elements if left is greater
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

با اجرای این کد خروجی زیر در کنسول چاپ می شود:

Unsorted array: [8, 2, 6, 4, 9, 1]
Sorted array: [1, 2, 4, 6, 8, 9]

در این پیاده سازی مرتب سازی حباب، ما هر بار آرایه را تکرار می کنیم حتی اگر قبلا مرتب شده باشد. ما می‌توانیم کد را بیشتر بهینه کنیم تا پس از مرتب‌سازی آرایه، مرتب‌سازی متوقف شود.

مرتب سازی حباب بهینه شده

public static void bubbleSortOptimised(int[] arr){
        int size = arr.length;

        // loop through array size-1 times
        for (int i = 0; i < size - 1; i++) {
            boolean swapped = false; // track swapping

            // loop until end of unsorted elements
            for (int j = 0; j < size - i - 1; j++) {
                // swap left and right elements if left is greater
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;

                    swapped = true;
                }
            }

            // if there was no swap, then the array is already sorted
            if(!swapped) break;
        }
    }

با این پیاده سازی، اگر بخواهیم یک آرایه از قبل مرتب شده را مرتب کنیم، فقط یک بار تکرار می کنیم و زمانی که مرتب سازی انجام نشد متوقف می شویم.

پیچیدگی مرتب سازی حباب

پیچیدگی زمانی:

بهترین مورد (O(n)):

بهترین حالت زمانی است که آرایه ورودی از قبل مرتب شده باشد. الگوریتم فقط یک بار از طریق آرایه تکرار می شود تا بررسی کند که آیا مرتب شده است و هیچ تعویضی انجام نمی دهد.

میانگین مورد (O(n²)):

این زمانی است که عناصر آرایه ورودی به ترتیب تصادفی هستند. الگوریتم باید چندین بار تکرار کند و برای مرتب‌سازی آرایه، تعویض‌ها را انجام دهد.

بدترین حالت (O(n²)):

بدترین حالت زمانی است که آرایه ورودی به ترتیب معکوس مرتب شود. الگوریتم می سازد n-1 تکرار می کند و حداکثر تعداد تعویض را انجام می دهد.

پیچیدگی فضایی O(1):

مرتب‌سازی حباب‌ها یک الگوریتم مرتب‌سازی در محل است، یعنی به هیچ حافظه اضافی متناسب با اندازه آرایه ورودی نیاز ندارد.

نتیجه گیری

Bubble Sort یک الگوریتم ساده برای درک و پیاده سازی است. با این حال، استفاده از مرتب سازی حباب در هنگام کار با مجموعه داده های بزرگ به دلیل پیچیدگی زمانی زیاد مناسب نیست. هنگام کار با مجموعه داده های کوچک یا زمانی که به پیچیدگی اهمیت نمی دهید، از مرتب سازی حباب استفاده کنید.