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

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

مقدمه

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

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

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

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

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

مرحله اول مرتب سازی حبابی برای مثال فوق به صورت زیر است.

مرتب سازی حبابی Bubble Sort

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

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

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

الگوریتم Bubble Sort

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

مرتب سازی حبابی Bubble Sort

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

الگوریتم Bubble Sort چیست؟

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

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

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

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

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

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

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

 

مطالب زیر را حتما بخوانید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.