مرتب‌سازی حبابی
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی ساده‌است که فهرست را پشت سرهم پیمایش می‌کند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابه‌جایشان کند. در این الگوریتم این کار باید تا زمانی که هیچ جابه‌جایی در فهرست رخ ندهد، ادامه یابد و در آن زمان فهرست مرتب شده‌است. این مرتب‌سازی از آن رو حبابی نامیده می‌شود که هر عنصر با عنصر کناری خود سنجیده‌شده و درصورتی که از آن کوچک‌تر باشد جای خود را به آن می‌دهد و این کار همچنان پیش می‌رود تا کوچک‌ترین عنصر به پایین فهرست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند (یا به رتبه‌ای بالاتر روند یا به پایین‌تر فهرست رانده شوند) این عمل همانند پویش حباب به بالای مایع است.
این مرتب‌سازی از آن رو که برای کار با عناصر آن‌ها را با یکدیگر می‌سنجد، یک مرتب‌سازی سنجشی است.
با فرض داشتن formula_1 عضو در فهرست، در بدترین حالت formula_2 عمل لازم خواهد بود.
بدترین زمان اجرا و پیچیدگی متوسط مرتب‌سازی حبابی هر دو formula_3می‌باشند که در آن n تعداد عناصری است که باید مرتب شوند. الگوریتم‌های مرتب‌سازی بسیاری وجود دارند که بدترین زمان اجرای آن‌ها از این بهتر است یا پیچیدگی متوسط آن‌ها formula_4 است. حتی بقیه الگوریتم‌های مرتب‌سازی از formula_3 مثل مرتب‌سازی درجی، عملکرد بهتری نسبت به مرتب‌سازی حبابی از خود نشان می‌دهند.
در مرتب‌سازی حبابی موقعیت عناصر درون فهرست نقش بسزایی در تعیین عملکرد آن دارد. از آنجایی که عناصر بزرگ در ابتدای فهرست به سرعت جابجا (swap) می‌شوند، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی‌کنند. اگرچه عناصر کوچک نزدیک به آخر فهرست (که باید به سمت ابتدای فهرست بیایند) بسیار کند حرکت می‌کنند. این تفاوت در سرعت به حدی است که به عناصر بزرگ، خرگوش‌ها، و به عناصر کوچک، لاک‌پشت‌ها می‌گویند. تلاش بسیاری انجام شده که سرعت حرکت لاک‌پشت‌ها در مرتب‌سازی حبابی افزایش یابد. از جمله می‌توان از [Cocktail Sort] نام برد که در این زمینه بسیار خوب عمل می‌کند ولی بدترین زمان اجرای آن هنوز formula_3 است. [مرتب‌سازی شانه‌ای] عناصر بزرگ با فاصله‌های زیاد را مقایسه می‌کند و لاک‌پشت‌ها را با سرعت فوق‌العاده‌ای حرکت می‌دهد سپس با کم‌تر و کم‌تر کردن این فاصله‌ها فهرست را به سرعت مرتب می‌کند، به‌طوری‌که سرعت متوسط آن قابل مقایسه با الگوریتم‌های پر سرعتی مثل مرتب‌سازی سریع می‌باشد.
اجازه بدهید یک آرایه از عددهای “۵, ۱, ۴, ۲, ۸” اختیار کنیم و آن را به ترتیب صعودی با استفاده از مرتب‌سازی حبابی مرتب کنیم. در هر مرحله عناصری که در حال مقایسه شدن با یکدیگر هستند پر رنگ تر نشان داده شده‌اند:
گذر اول:
حالا آرایه مرتب شده‌است، ولی الگوریتم هنوز نمی‌داند که این کار کامل انجام شده‌است یا نه، که برای فهمیدن احتیاج به یک گذر کامل بدون هیچ جابجایی (swap) داریم:
گذردوم
در نهایت آرایه مرتب شده‌است و الگوریتم می‌تواند پایان پذیرد.
بیان سادهٔ شبه کد مرتب‌سازی حبابی:
سورس مرتب‌سازی حبابی به زبان ++C به شرح زیر است:int main()
این سورس یک عدد گرفته و به تعداد همان عدد از ورودی دریافت می‌کند و آن‌ها را با روش Bubble sort مرتب می‌کند. void read_list(int a[],int n){ void print_list(int a[],int n){ //-------------------------------------------------------------------------- void bubble_sort(int a[],int n){ int main(){
return 0; //-------------------------------------------------------------------------- این الگوریتم در بدترین حالت از مرتبهٔ formula_7 است. چون در بدترین حالت هر عنصر باید formula_8 بار فهرست را بپیماید.
بهترین حالت این است که فهرست مرتب شده‌باشد که در این حالت الگوریتم از مرتبه formula_9 است.
کارایی مرتب‌سازی حبابی با رعایت شرایط زیر می‌تواند افزایش قابل ملاحظه‌ای داشته باشد. اول این که توجه داشته باشید بعد از هر مقایسه (و احتمالاً جابجایی) در هر پیمایش، بزرگ‌ترین عنصری که از آن عبور می‌کنیم در آخرین موقعیت پیمایش شده قرار خواهد گرفت. از این رو بعد از اولین پیمایش بزرگ‌ترین عنصر آرایه در آخرین خانه آن خواهد بود. این یعنی با داشتن فهرستی با اندازه formula_1، پس از اولین پیمایش، n-امین عنصر در مکان نهایی اش خواهد بود. بنا بر استقرا بقیه formula_8 عنصر باقی‌مانده به همین صورت مرتب می‌شوند که بعد از پیمایش دوم، formula_8 امین عنصر در جای نهایی خودش خواهد بود، و الی آخر. پس طول هر پیمایش می‌تواندبه اندازه یک مرحله کم‌تر از پیمایش قبل از خودش باشد و به جای آنکه هر بار تمامی عناصر را تا انتهای آرایه بپیماییم، عناصری که در موقعیت پایانی خود هستند و از به هیچ عنوان جابجا نمی‌شوند چشم پوشی کنیم. با تبدیل این روش به شبه کد خواهیم داشت: procedure bubbleSort(A: list of sortable items) defined as: end procedure
زمان اجرای این روش هنوز هم formula_3 است ولی در بدترین حالت (وقتی آرایه ورودی به صورت معکوس مرتب شده باشد) زمان اجرای آن دو برابر سریع تر از حالت عادی الگوریتم می‌باشد.
مرتب‌سازی زوج-فرد پیاده‌سازی این الگوریتم به شیوهٔ موازی است.