در الگوریتم مرتب سازی حبابی هر عنصر با عنصر کناری خود سنجیده‌شده و درصورتی که از آن کوچک‌تر باشد جای خود را به آن می‌دهد و این کار ادامه می یابد تا کوچک‌ترین عنصر به پایین لیست برسد و بقیه نیز به ترتیب در جای خود قرار گیرند. این الگوریتم برای مجموعه داده‌های بزرگ مطلوب نیست، زیرا پیچیدگی حالت میانگین و بدترین حالت آن برابر با (Ο(n2 است که در آن n تعداد آیتم‌هایی است که باید مرتب شوند.

طرز کار الگوریتم مرتب سازی حبابی

به عنوان مثال یک آرایه نامرتب را در نظر می‌گیریم.

مرتب‌سازی حبابی کار خود را با نخستین دو عنصر آغاز می‌کند و آن‌ها را مقایسه می‌کند تا ببیند کدام یک بزرگ‌تر است

در این مثال 33 از 14 بزرگ‌تر است و از این رو این دو عنصر هم‌اینک در وضعیت مرتب هستند، سپس دو مقدار 33 و 27 را مقایسه می‌کنیم

درمی‌یابیم که 27 کوچک‌تر از 33 است و لذا موقعیت این دو عنصر باید تعویض شود

سپس 33 و 35 را مقایسه می‌کنیم. مشخص است که این دو مقدار در وضعیت مرتب هستند

سپس دو مقدار بعدی یعنی 35 و 10 مقایسه می‌شوند

می‌دانیم که 10 کوچک‌تر از 35 است. از این رو این دو مقدار مرتب نیستند

این دو مقدار را تعویض می‌کنیم. درمی‌یابیم که به انتهای آرایه رسیده‌ایم. پس از یک چرخه، آرایه به صورت زیر درمی‌آید

این چرخه را آنقدر ادامه می دهیم تا لیست کاملا مرتب شده باشد.

شبه کد

procedure bubbleSort(A: list of sortable items) defined as:
   do
      swapped:= false
      for each i in 0 to length(A) - 2 inclusive do:
         if A[ i ]> A[ i + 1 ] then
            swap(A[ i ], A[ i + 1 ])
            swapped:= true
         end if
      end for
   while swapped
end procedure

پیاده سازی الگوریتم مرتب سازی حبابی به زبان #C

static void Main(string[] args)
        {
            int[] bList= { 14, 33, 27, 5, 35, 10, 40 };

            bool swapped = false;

            do
            {
                swapped = false;
                for(int counter = 0; counter < bList.Count() - 1; counter++)
                {
                    if (bList[counter] > bList[counter + 1])
                    {
                        int temp = bList[counter];
                        bList[counter] = bList[counter + 1];
                        bList[counter + 1] = temp;
                        swapped = true;
                    }
                }
            } while (swapped==true);

            for(int pCounter = 0; pCounter < bList.Count(); pCounter++)
            {
                Console.WriteLine(bList[pCounter]);
            }
            Console.ReadKey();
        }

منابع:

ویکی پدیا

Tutorials Point