الگوریتم مرتب سازی حبابی Bubble Sort
مقدمه
در این پست به توضیح و تشریح الگوریتم مرتب سازی حبابی Bubble Sort خواهیم پرداخت. مرتب سازی حبابی یکی از روشهای مرتبسازی در آرایه ها است که به آن روش تعویض استاندارد یا Standard Exchange نیز میگویند. این روش مرتب سازی شامل چند مرحله است که در هر مرحله یک عنصر از لیست به طور قطعی در محل مناسب خود قرار میگیرد. به بیان دیگر که در آن، جفت عنصرهای همسایه با یکدیگر مقایسه شده و در صورتی که دارای ترتیب صحیحی نباشند، با یکدیگر جا به جا میشوند.
مثال قدم به قدم
آرایه با 6 عنصر یعنی n=6 را در نظر بگیرید اکنون میخواهیم این آرایه به صورت صعودی یعنی از کوچک به بزرگ مرتب کنیم این آرایه با اندیس های 0 تا 5 (شماره های قرمز) و عناصر داخل (شماره های مشکی) آن طبق شکل زیر مشخص است.
برای مرتب سازی این آرایه 5 مرحله نیاز داریم یعنی n-1 مرحله و در هر مرحله به 5 مقایسه (n-1) بین اعضای آن نیاز خواهیم داشت. پس در کل به 25 مقایسه نیاز داریم هر چند ممکن است در نصف راه هم به آرایه مرتب برسیم ولی تا پایان الگوریتم این مقایسه ها بایستی انجام پذیرد. ( البته در پیاده سازی تنها به 15 مقایسه نیاز داریم ) با استفاده از شکل ها پیش می رویم.
مرحله اول مرتب سازی حبابی برای مثال فوق به صورت زیر است.
مرحله دوم مرتب سازی
مرحله سوم مرتب سازی
مرحله چهارم مرتب سازی
مرحله 5 مرتب سازی
با مشاهده این مثال بخوبی متوجه شدید که در هر مرحله نیاز به 5 مقایسه داریم. در مرحله پایانی هیچ تغییر یا جابجایی بر رو آرایه انجام نشد اگر فرض بر این باشد طول آرایه بیشتر از 6 باشد و در مرحله مثلاً 4 ام آرایه مرتب باشد پس مراحل بعدی عملاً بیهوده خواهد بود یعنی الگوریتم مقایسه های بیهوده ای را تا آخر انجام می دهد برای اجتناب از این کار می توان در هر مرحله یک متغییری را تعریف کرد که اگر در مرحله ای هیچ جابجایی انجام نشود ( یعنی آرایه مرتب شده) پس Breack کن یعنی از مراحل بعدی صرف نظر کن.
پیچیدگی زمانی الگوریتم
الگوریتم مرتب سازی حبابی برای مجموعه دادههای بزرگ مناسب نیست، زیرا پیچیدگی زمانی آن در حالت میانگین و بدترین حالت برابر با (Ο(n2 است، که در آن 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; }
در این آموزش الگوریتم مرتب سازی حبابی Bubble Sort بصورت کامل با یک مثال عملی توضیح داده شد این آموزش بصورت اختصاصی از سایت پی استور منتشر شده است.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
با سلام عرض ادب به استاد گرامی
استاد از شما سوالی داشتم
این سوال چطوری حل میشه؟
پیچیدگی زمانی الگوریتم مرتب سازی حبابی را تحلیل کنید.(ابتدا کد الگوریتم را بنویسید سپس پیچیدگی آنرا تحلیل کنید)