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

مرتب سازی حبابی $(Bubble sort)$ نوعی مرتب‌سازی مقایسه‌ای ساده است که در آن فهرست داده‌ها را تا جایی که مرتب شوند پیمایش می کند و عناصر مجاور را باهم مقایسه می‌کند واگر در ترتیب نادرست بودند آن‌ها را جابه‌جا می‌کند.

این مرتب سازی از این جهت حبابی نامیده می‌شود که عناصر کوچک‌تر درآن مانند حباب به بالای لیست می‌آیند. باوجود این که الگوریتم آن بسیار ساده است اما به علت کندی ناکارآمد می‌باشد و برای حل بیش‌تر مسائل مناسب نیست.

شبه کد این الگوریتم به صورت روبه‌رو می باشد:

در شبه کد بالا هر بار که حلقه تمام می شود بزرگ‌ترین عنصر به ته آرایه می‌رسد و در حلقه‌های بعدی وقتی به این خانه می‌رسیم جابه‌جایی صورت نمی‌گیرد.

این الگوریتم را می‌توان با اندکی تغییر بهتر کرد چون که در مرحله ی xم , x‌مین بزرگ‌ترین عنصر پیدا می‌شود پس نیاز نیست که در هر بار اجرای حلقه تا پایان لیست برویم و شبه کد زیر آن را دقیق‌تر توصیف می‌کند:

در بدترین حالت الگوریتم باید n-1 بار اجرا شود و در مرحله‌ی iم باید n-i عمل انجام شود پس در مجموع بهn(n-1)/2 که از $O(n^2)$ عمل می باشد نیاز است پس در بدترین حالت از $O(n^2)$ می‌باشد. در بهترین حالت تنها یکبار وارد حلقه می‌شود و از $O(n)$ می‌باشد. در حالت میانگین نیز از $O(n^2)$ می‌باشد. الگوریتم‌های مرتب‌سازی بسیاری وجود دارند که بدترین زمان اجرای آن‌ها از این بهتر است یا پیچیدگی متوسط آن‌ها $O(nlgn)$ است. حتی بقیه اگوریتم‌های مرتب‌سازی از $O(n^2)$ مثل مرتب‌سازی درجی، عملکرد بهتری نسبت به مرتب‌سازی حبابی از خود نشان می‌دهند.

bubble_Sort.cpp

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn=1000+100;
int n,a[maxn];
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        bool swaped=0;
        for(int j=1;j<=n-i;j++)
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                swaped=true;
            }
        if(!swaped)
            break;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<endl;
 
    return 0;
}

• https://en.wikipedia.org/wiki/Bubble_sort