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

به علت سادگی ، مرتب سازی حبابی اغلب برای معرفی مفهوم یک الگوریتم ، یا یک الگوریتم مرتب سازی و حتی آموزشهای مقدماتی برای دانشجویان علوم کامپیوتر استفاده می شود. با این وجود ، بعضی از محققین مانند Owen Astrachan  عملیات سنگینی را روی این الگوریتم پیاده کردند ( مانند طول آرایه بسیار زیاد ) تا ثابت کنند که این الگوریتم ناکارآمد است و نباید در آموزش علوم کامپیوتر مورد استفاده قرار گیرد.

Donald Knuth در کتاب مشهورش “The Art of Computer Programming” ، مرتب سازی حبابی را این گونه تفسیر می کند :

" به نظر می رسد که مرتب سازی حبابی به غیر از یک نام جذاب و حقیقتی که منجر به طرح بعضی مسائل نظری جالب می شود ، چیزی برای عرضه ندارد."

مرتب سازی حبابی از نظر مجانبی معادل زمان اجرای مرتب سازی درجی در بدترین حالت است ، اما دو الگوریتم از نظر تعداد جابجایی ها به شدت با هم فرق می کنند. نتایج عملی مانند کاری که Astrachan  انجام داد نشان می دهد که مرتب سازی درجی حتی بر روی آرایه های تصادفی نیز بهتر عمل می کند. به همین دلیل ، بسیاری از کتب درسی جدید ، دیگر از مرتب سازی حبابی استفاده نمی کنند و بجای آن مرتب سازی درجی را آموزش می دهند.

همچنین مرتب سازی حبابی با CPU های مدرن بطور ضعیفی تعامل می کنند. مرتب سازی حبابی حداقل دو برابر مرتب سازی درجی احتیاج به نوشتن دارد و در نتیجه دو برابر آن نیز cache را هدر می دهد و به صورت مجانبی باعث branch mispredictions  یا عدم پیش بینی شاخه ای می شود. تحقیقات به عمل آمده توسط Astrachan  بر روی مرتب سازی رشته ها در Java نشان می دهد که مرتب سازی حبابی 5 برابر از مرتب سازی درجی و حدود 40% از مرتب سازی انتخابی کندتر است.

 در ادامه به صورت تصویری نحوه عملکرد مرتب سازی حبابی را تشریح می کنم . از دوستان عزیزم خواهشمندم برای بهبود کیفیت کارهای بعدی نظر خود را در مورد این پست حتماْ به بنده انتقال بدهند.

توجه : برای مشاهده تصاویر به صورت متحرک یا Gif بر روی آنها کلیک کنید.

تصویر ۱ :

در این شکل ۵ عنصر به صورت مرحله به مرحله مرتب می شوند:

تصویر ۲ :

در این تصویر مرتب سازی حبابی همراه با اجرای همزمان کد نمایش داده می شود. به نظر من این تصویر برای آموزش بسیار مناسب است زیرا همزمان می توانید نحوه اجرای کد را نیز ببینید.

تصویر ۳ :

این تصویر و تصاویر بعدی به صورت میله ای می باشند. یعنی ارتفاع هر میله بیانگر مقدار آن است.

تصویر ۴ :

تصویر ۵ : و این هم آخرین تصویر که خیلی کوچک و گویا است.

امیدوارم تو این پست تونسته باشم قدم مفیدی در این زمینه بر داشته باشم.

از دوستان عزیز خواهشمندم من رو از پیشنهادات و انتقادات خودشون محروم نکنند.

در پست بعدی در مورد مرتب سازی درجی بحث خواهم کرد.