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

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

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

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

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

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

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

برای مشاهده بقیه مراحل پیچیدگی زمانی و محاسباتی و سورس کد این مرتب سازی به پست ما در سایت پی استور با عنوان الگوریتم مرتب سازی حبابی Bubble Sort مراجعه فرمایید.