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

بدترین زمان اجرا و پیچیدگی متوسط مرتب‌سازی حبابی هر دو ${\displaystyle O(n^2)}$

در مرتب‌سازی حبابی موقعیت عناصر درون فهرست نقش بسزایی در تعیین عملکرد آن دارد. از آنجایی که عناصر بزرگ در ابتدای فهرست به سرعت جابجا (swap) می‌شوند، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی‌کنند. اگرچه عناصر کوچک نزدیک به آخر فهرست (که باید به سمت ابتدای فهرست بیایند) بسیار کند حرکت می‌کنند. این تفاوت در سرعت به حدی است که به عناصر بزرگ، خرگوش‌ها، و به عناصر کوچک، لاک‌پشت‌ها می‌گویند.
تلاش بسیاری انجام شده که سرعت حرکت لاک‌پشت‌ها در مرتب‌سازی حبابی افزایش یابد. از جمله می‌توان از [Cocktail Sort] نام برد که در این زمینه بسیار خوب عمل می‌کند ولی بدترین زمان اجرای آن هنوز ${\displaystyle O(n^2)}$

اجازه بدهید یک آرایه از عددهای “۵, ۱, ۴, ۲, ۸” اختیار کنیم و آن را به ترتیب صعودی با استفاده از مرتب‌سازی حبابی مرتب کنیم. در هر مرحله عناصری که در حال مقایسه شدن با یکدیگر هستند پر رنگ تر نشان داده شده‌اند:

گذر اول:

(۱, ۵, ۴, ۲, ۸) <= (۵, ۱, ۴, ۲, ۸)

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

(۱, ۴, ۵, ۲, ۸) <= (۱, ۵, ۴, ۲, ۸)

(۱, ۴, ۲, ۵, ۸) <= (۱, ۴, ۵, ۲, ۸)

(۱, ۲, ۴, ۵, ۸) <= (۱, ۴, ۲, ۵, ۸)

حالا آرایه مرتب شده‌است، ولی الگوریتم هنوز نمی‌داند که این کار کامل انجام شده‌است یا نه، که برای فهمیدن احتیاج به یک گذر کامل بدون هیچ جابجایی (swap) داریم:

گذردوم

(۱, ۲, ۴, ۵, ۸) <= (۱, ۲, ۴, ۵, ۸)

(۱, ۲, ۴, ۵, ۸) <= (۱, ۲, ۴, ۵, ۸)

(۱, ۲, ۴, ۵, ۸) <= (۱, ۲, ۴, ۵, ۸)

(۱, ۲, ۴, ۵, ۸) <= (۱, ۲, ۴, ۵, ۸)

در نهایت آرایه مرتب شده‌است و الگوریتم می‌تواند پایان پذیرد.

بیان سادهٔ شبه کد مرتب‌سازی حبابی:

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 به شرح زیر است:

#include <iostream>

int main()
{
    int len=10;
    int a[len],i,j,temp;
    
    for(i=0;i<len;i++)
    {
        std::cin>>a[i];    // دریافت اعضای آرایه (لیست مورد نظر) برای مرتب‌سازی
    }
    
    for(i=len-2;i>=0;i--)
    {
        for(j=0;j<=i;j++)
        {
            if(a[j]>a[j+1])   //مقایسهٔ تک به تک هر عضو آرایه با عضو کناری
            {
                temp=a[j];  //و جابه‌جایی اعضا یا یکدیگر در صورت برقراری شرط
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    
    for(i=0;i<len;i++)
    {
        std::cout<<a[i];   //چاپ اعضا
    }

    return 0;
}

مثالی از مرتب‌سازی

این سورس یک عدد گرفته و به تعداد همان عدد از ورودی دریافت می‌کند و آن‌ها را با روش Bubble sort مرتب می‌کند.

# include<cstdio>
#include<cstdlib>

//--------------------------------------------------------------------------
void read_list(int a[],int n){
 int i;
 for(i=0;i<n;i++){
  printf("\n\n\t ENTER THE ELEMENT [%d] :: ",i);
  scanf("%d",&a[i]);
 }
}
//--------------------------------------------------------------------------
void print_list(int a[],int n){
 int i;
 for(i=0;i<n;i++)
   printf("\t%d",a[i]);
}
//--------------------------------------------------------------------------
void bubble_sort(int a[],int n){
 int i,j,temp;
 for(i=0;i<n-1;i++){
  for(j=0;j<n-1;j++)
   if(a[j]>a[j+1]){
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
   }
  printf("\n\n\t PASS %d :: ",i);
  print_list(a,n);
 }
}
//--------------------------------------------------------------------------
int main(){
 int a[20],n;
 
 printf("\n\n\t ENTER THE ARRAY LENGTH :: ");
 scanf("%d",&n);

 read_list(a,n);

 printf("\n\n\t THE ARRAY ELEMENTS ARE AS FOLLOWS :: ");
 print_list(a,n);

 bubble_sort(a,n);

 printf("\n\n\t THE SORTED LIST IS :: ");
 print_list(a,n);
return 0;
}
//--------------------------------------------------------------------------

بدترین حالت

این الگوریتم در بدترین حالت از مرتبهٔ ${\displaystyle \mathrm{\Theta }(n^2)}$

بهترین حالت

بهترین حالت این است که فهرست مرتب شده‌باشد که در این حالت الگوریتم از مرتبه ${\displaystyle O(n)}$

کارایی مرتب‌سازی حبابی با رعایت شرایط زیر می‌تواند افزایش قابل ملاحظه‌ای داشته باشد.
اول این که توجه داشته باشید بعد از هر مقایسه (و احتمالاً جابجایی) در هر پیمایش، بزرگ‌ترین عنصری که از آن عبور می‌کنیم در آخرین موقعیت پیمایش شده قرار خواهد گرفت. از این رو بعد از اولین پیمایش بزرگ‌ترین عنصر آرایه در آخرین خانه آن خواهد بود.
این یعنی با داشتن فهرستی با اندازه ${\displaystyle n}$

procedure bubbleSort(A: list of sortable items) defined as:
  n:= length(A)
  do
    swapped:= false
    n:= n - 1
    for each i in 0 to n - 1  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

زمان اجرای این روش هنوز هم ${\displaystyle O(n^2)}$

مرتب‌سازی زوج-فرد پیاده‌سازی این الگوریتم به شیوهٔ موازی است.

• الگوریتم‌های مرتب‌سازی
• مرتب‌سازی سنجشی

• مرتب‌سازی حبابی در ۲۰ زبان برنامه‌نویسی
• مرتب‌سازی حبابی