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

مقدمه

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

ویژگی‌های مرتب سازی حبابی ( روش تعویض استاندارد)

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

مثال قدم به قدم

آرایه با ۶ عنصر یعنی n=6 را در نظر بگیرید اکنون می‌خواهیم این آرایه به صورت صعودی یعنی از کوچک به بزرگ مرتب کنیم این آرایه با اندیس‌های ۰ تا ۵ (شماره های قرمز) و عناصر داخل (شماره های مشکی) آن طبق شکل زیر مشخص است.

برای مرتب سازی این آرایه ۵ مرحله نیاز داریم یعنی n-1 مرحله و در هر مرحله به ۵ مقایسه (n-1) بین اعضای آن نیاز خواهیم داشت. پس در کل به ۲۵ مقایسه نیاز داریم هر چند ممکن است در نصف راه هم به آرایه مرتب برسیم ولی تا پایان الگوریتم این مقایسه‌ها بایستی انجام پذیرد. ( البته در پیاده سازی تنها به ۱۵ مقایسه نیاز داریم ) با استفاده از شکل‌ها پیش می‌رویم. مرحله اول مرتب سازی حبابی برای مثال فوق به صورت زیر است.

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

مرحله چهارم مرتب سازی

مرحله ۵ مرتب سازی

با مشاهده این مثال بخوبی متوجه شدید که در هر مرحله نیاز به ۵ مقایسه داریم. در مرحله پایانی هیچ تغییر یا جابجایی بر رو آرایه انجام نشد اگر فرض بر این باشد طول آرایه بیشتر از ۶ باشد و در مرحله مثلاً ۴ام آرایه مرتب باشد پس مراحل بعدی عملاً بیهوده خواهد بود یعنی الگوریتم مقایسه‌های بیهوده‌ای را تا آخر انجام می‌دهد برای اجتناب از این کار می‌توان در هر مرحله یک متغییری را تعریف کرد که اگر در مرحله ای هیچ جابجایی انجام نشود ( یعنی آرایه مرتب شده) پس Breack کن یعنی از مراحل بعدی صرف نظر کن. در راستای همین موضوع می‌توانید از فایل آماده موجود در لینک زیر بهره ببرید و ارائه‌ای جذاب داشته باشید.

• پاورپوینت الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی — کلیک کنید.

پیچیدگی زمانی الگوریتم

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

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

#include <stdio.h> 
  
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
  
// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
   int i, j; 
   for (i = 0; i < n-1; i++)       
  
       // Last i elements are already in place    
       for (j = 0; j < n-i-1; j++)  
           if (arr[j] > arr[j+1]) 
              swap(&arr[j], &arr[j+1]); 
} 
  
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
}

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

#include <stdio.h> 
  
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
  
// An optimized version of Bubble Sort 
void bubbleSort(int arr[], int n) 
{ 
   int i, j; 
   bool swapped; 
   for (i = 0; i < n-1; i++) 
   { 
     swapped = false; 
     for (j = 0; j < n-i-1; j++) 
     { 
        if (arr[j] > arr[j+1]) 
        { 
           swap(&arr[j], &arr[j+1]); 
           swapped = true; 
        } 
     } 
  
     // IF no two elements were swapped by inner loop, then break 
     if (swapped == false) 
        break; 
   } 
} 
  
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
}

با مشاهده این مثال بخوبی متوجه شدید که در هر مرحله نیاز به ۵ مقایسه داریم. در مرحله پایانی هیچ تغییر یا جابجایی بر رو آرایه انجام نشد اگر فرض بر این باشد طول آرایه بیشتر از ۶ باشد و در مرحله مثلاً ۴ ام آرایه مرتب باشد پس مراحل بعدی عملاً بیهوده خواهد بود یعنی الگوریتم مقایسه‌های بیهوده‌ای را تا آخر انجام می‌دهد برای اجتناب از این کار می‌توان در هر مرحله یک متغییری را تعریف کرد که اگر در مرحله‌ای هیچ جابجایی انجام نشود ( یعنی آرایه مرتب شده) پس Breack کن یعنی از مراحل بعدی صرف نظر کن.

در این آموزش الگوریتم مرتب سازی حبابی Bubble Sort بصورت کامل با یک مثال عملی توضیح داده شد این آموزش بصورت اختصاصی از سایت پی استور منتشر شده است.

پاورپوینت مقایسه الگوریتم های مرتب سازی (Sorting algorithm)

پاورپوینت مقایسه الگوریتم های مرتب سازی (Sorting algorithm)

کلیک کنید