مرتب سازی حبابی ( Bubble Sort ) چیست ؟

مرتب سازی حبابی یا Bubble Sort یک الگوریتم ساده برای مرتب سازی است . این الگوریتم مرتب سازی بر اساس مقایسه دو المنت مجاور کار می‌کند و در صورتیکه دو المنت مجاور در آرایه بصورت مرتب قرار نگرفته باشند ، جای آن ها را عوض می‌کند. استفاده از این الگوریتم به علت پیچیدگی O(n²) ، برای آرایه های طولانی توصیه نمی‌شود.

مرتب سازی حبابی چگونه کار می‌کند ؟

بعنوان مثال آرایه‌ی نامرتب زیر را در نظر می‌گیریم. اجرای مرتب سازی حبابی n² مرحله طول خواهد کشید ولی ما در اینجا مختصر و مفید کار را دنبال خواهیم کرد . نکته قابل توجه این است که ما میخواهیم آرایه را بصورت نزولی ( از کم به زیاد ) مرتب کنیم و با کمی تغییر در الگوریتم و کد می‌توان روند کار را برعکس کرد.

همونطور که گفته شد ، پیچیدگی این الگوریتم O(n²) هست ! بنابراین مراحل زیر بعد از رسیدن به خانه‌ی آخر به تعداد خانه‌های آرایه تکرار خواهد شد. ( در اینجا ۵ بار ).

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

در اینجا ۳۳ از ۱۴ بزرگتر است پس در حال حاضر در جایگاه درستی قرار دارد. بعد از آن ، سراغ مقایسه‌ی ۳۳ و ۲۷ می‌رویم.

همانطور که مشخص است ، ۲۷ از ۳۳ کوچکتر است پس باید جایش با ۳۳ عوض شود.

آرایه‌ی جدید به این شکل خواهد بود:

باتوجه به آرایه‌ی جدید ، در مرحله‌ی بعدی به سراغ مقایسه‌ی ۳۳ و ۳۵ می‌رویم. و به این موضوع پی می‌بریم که در جای درست خود قرار دارند ( بصورت نزولی مرتب شده‌اند ) .

در مرحله‌ی بعدی به سراغ دو المنت بعدی آرایه می‌رویم ( ۳۵ و ۱۰ ).

همونطور که میدانیم ، ۱۰ از ۳۵ کوچکتر است ! پس جای این دو با یکدیگر عوض می‌شود.

بعد از اینکه به خانه‌ی آخر آرایه رسیدیم ، این عملیات یکبار دیگر تکرار خواهد شد ( در کل این مراحل به تعداد خانه‌های آرایه تکرار می‌شوند ). بعد از یک تکرار آرایه به این شکل درخواهد آمد :

در تکرار دوم می‌بینید که خانه‌های مجاور در آرایه به چه شکل با هم جابجا می‌شوند :

آرایه بعد از تکرار سوم :

و در نهایت بعد از تکرار چهارم ( در مجموع ۵ بار تکرار ) آرایه به مرتب سازی نیاز نخواهد داشت و تمامی المنت‌های آرایه بصورت نزولی مرتب شده اند :

حال می‌توان به ساختار الگوریتم و کد مرتب سازی حبابی اشاره کرد .

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

ما یک لیست را به عنوان آرایه‌ای با n خانه به الگوریتم وارد می‌کنیم. با این تصور که در قبل تابعی را برای جابجایی دو المنت از آرایه تعریف کردیم به الگوریتم bubble sort نگاهی می‌اندازیم :

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

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

کد مرتب سازی حبابی به زبان C ، کدی مانند کد زیر خواهد بود :

 
#include <stdio.h>
 
int main()
{
  int array[100], n, c, d, swap;
 
  printf("Enter number of elements\n");
  scanf("%d", &n);
 
  printf("Enter %d integers\n", n);
 
  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);
 
  for (c = 0 ; c < ( n - 1 ); c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use < */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
      }
    }
  }
 
  printf("Sorted list in ascending order:\n");
 
  for ( c = 0 ; c < n ; c++ )
     printf("%d\n", array[c]);
 
  return 0;
}

و اگر بخواهیم در کد خود از تابع مرتب سازی حبابی استفاده کنیم ، می‌توانیم از کد زیر بهره ببریم :

#include <stdio.h>
 
void bubble_sort(long [], long);
 
int main()
{
  long array[100], n, c, d, swap;
 
  printf("Enter number of elements\n");
  scanf("%ld", &n);
 
  printf("Enter %ld integers\n", n);
 
  for (c = 0; c < n; c++)
    scanf("%ld", &array[c]);
 
  bubble_sort(array, n);
 
  printf("Sorted list in ascending order:\n");
 
  for ( c = 0 ; c < n ; c++ )
     printf("%ld\n", array[c]);
 
  return 0;
}
 
void bubble_sort(long list[], long n)
{
  long c, d, t;
 
  for (c = 0 ; c < ( n - 1 ); c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (list[d] > list[d+1])
      {
        /* Swapping */
 
        t         = list[d];
        list[d]   = list[d+1];
        list[d+1] = t;
      }
    }
  }
}

حرف پایانی

شما می‌توانید از این الگوریتم برای مرتب سازی رشته‌ها ( string ) هم استفاده کنید ولی با توجه به پیچیدگی این الگوریتم ، بهتر است از الگوریتم‌های دیگر با پیچیدگی کمتر استفاده کنید !

امیدوارم که این آموزش نظر شما را جلب کرده باشد