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

فرض کنید n داده داریم که می خواهیم به صورت صعودی مرتب شوند. عنصر اول رو با دومی مقایسه و در صورتی که اولی بزرگتر باشد جاهاشون رو عوض می کنیم. همین کار رو با عناصر دوم و سوم انجام می دهید و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تموم شد بزرگترین عنصر بین داده ها به آخر لیست می رسد. حالا یک بار دیگه از اول این کار رو انجام می دهیم اما این بار تا عنصر  (n -1)ام ادامه می دهیم (عنصر  nام مرحله اول جای خودش رو پیدا کرده). باز هم این کار رو تا عنصر  (n - 2)ام تکرار می کنیم ، و بازهم ... تا اینکه بالاخره داده ها مرتب می شوند مثلا :

0 - 0 )    5 6 4 2

1 - 1 )    5 6 4 2

1 - 2 )    5 4 6 2

1 - 3 )    5 4 2 6

2 - 1 )    4 5 2 6

2 - 2 )    4 2 5 6

3 - 1 )    2 4 5 6

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می شوند شش مقایسه. در کل این روش n (n - 1) / 2 مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید :

0 - 0 )    0 7 1 3 5 4

1 - 1 )    0 1 7 3 5 4

1 - 2 )    0 1 7 3 5 4

1 - 3 )    0 1 3 7 5 4

1 - 4 )    0 1 3 5 7 4

1 - 5 )    0 1 3 5 4 7

2 - 1 )    0 1 3 5 4 7

2 - 2 )    0 1 3 5 4 7

2 - 3 )    0 1 3 5 4 7

2 - 4 )    0 1 3 4 5 7

3 - 1 )    0 1 3 4 5 7

3 - 2 )    0 1 3 4 5 7

3 - 3 )    0 1 3 4 5 7

4 - 1 )    0 1 3 4 5 7

4 - 2 )    0 1 3 4 5 7

5 - 1 )    0 1 3 4 5 7

همونطور که می بینید انتهای مرحله 2 داده ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله ای رسیدیم که هیچ جابجایی در اون رخ نداد  نتیجه می شه که داده ها مرتب هستن )مرحله سوم). پس بعد از مرحله 3 مطمئن می شیم که داده هامون مرتب شدن و نیازی به مراحل 4 و 5 نیست.

پیاده سازی (مرتب سازی حبابی)  در  c++

void bubble_sort ( int arr [ ] , int n )

{

  register int i , j , t , c ;

  for ( i = n - 2 ; i >= 0 ; i -- )

  {

    c = 0 ;

    for ( j = 0 ; j <= i ; j ++ )

      if ( arr [ j ] > arr [ j + 1 ] )

      {

        t = arr [ j ] ;

        arr [ j ] = arr [ j + 1 ] ;

        arr [ j + 1 ] = t ;

        c ++ ;

      }

      if ( c == 0 )

        break ;

  }

}

پیاده سازی (مرتب سازی حبابی) در پاسکال 

procedure bubble_sort ( var arr : array of integer ) ;

var

    i , j , c , t : integer ;

begin

    for i := high ( arr ) - 1 downto low ( arr ) do

    begin

        c := 0 ;

        for j := low ( arr ) to i do

            if arr[ j ] > arr[ j + 1 ] then

            begin

                t := arr [ j ] ;

                arr [ j ] := arr [ j + 1 ] ;

                arr [ j + 1 ] := t ;

                inc ( c ) ;

            end ;

        if c = 0 then

            break ;

    end ;

end ;

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

 اگر طول یک لیست ،n  فرض شود. همانطور که در الگوریتم حبابی مشاهد میگردد. دو حلقه تو در تو وجود دارد که اولین حلقه n-1  بار و دومین حلقه n/2  بار تکرار میشود      

n/2(n-1)=1/2(n^2-n) : تعداد مقایسه ها

تعداد تعویض ها در مرتب سازی حبابی :

در بهترین حالت(وقتی که لیست مرتب باشد) صفر است و در بدترین حالت( وقی که لیست به طور معکوس مرتب باشد) برابر با (n^2-n)2/3 و تعداد متوسط تعویضها برابر با (n^2-n)4/3 است. رابطه بدترین حالت به صورت زیر به دست آمده است.

تعداد مقایسه ها  =تعداد تعویضها

1/2(N^2-n)* 3     =     3/2(n^2-n)

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