Thuật toán nổi bọt

Sp xếp ni bt (bubble sort) là mt thut toán sp xếp đơn gin, so sánh hai phn t đu, nếu phn t đng trước ln hơn phn t đng sau thì đi ch chúng cho nhau. Tiếp tc làm như vy vi cp phn t tiếp theo cho đến cui tp hp d liu. Sau đó, quay li vi hai phn t đu cho đến khi không còn cn phi đi ch na. Nó có tên gi này t hình nh ca các “bt” khí nh hơn được ni lên trên. Nó s dng phép so sánh các phn t nên là mt sp xếp kiu so sánh.

Ví dụ:
Quá trình sắp xếp nổi bọt của 5 phần tử

Đề cho 1 dãy số gồm 5 số:
42,23,74,11,65 sắp xếp theo thứ tự tăng dần

Ta làm chi tiết như sau:
Giai đoạn 1 ( chạy cho 5 phần tử của dãy )
1.Đầu tiên so sánh 42 và 23 ,ta thấy 23 bé hơn nên đổi chỗ chúng cho nhau (“so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau”) ( cột 2 trong hình vẽ trên )
2.Sau đó so sánh 42 và 74 do 42<74 nên giữ nguyên vị trí ( cột 3 trong hình vẽ trên )
3.So sánh 74 với 11 ta thấy 11<74 nên đổi chỗ chúng cho nhau ( cột 4 trong hình vẽ trên )
4.Cuối cùng của giai đoạn này là so sánh 65 với 74 , 65<74 nên đảo vị trí chúng cho nhau ( cột 5 )
Giai đoạn 2 ( chạy cho 4 phần tử của dãy ,phần tử dưới cúng 74 làm xong rồi )
1.So sánh 23 và 42 do 23<42 nên vẫn giữ nguyên ( cột 6 )
2.So sánh 11 với 42 do 11 < 42 nên đổi vị trí chúng cho nhau ( cột 7 )
3.Cuối cùng của giai đoạn 2 là so sánh 42 và 65 do 42<65 nên vẫn giữ nguyen vị trí của chúng ( cột 8 )
Giai đoạn 3 ( chạy cho 3 phần tử )
1.So sánh 11 với 23 do 11<23 nên tróa chỗ cho nhau ( cột 9 )
2.So sánh 23 với 42 do 42> 23 nên vẫn giữ nguyên vị trí của chúng ( cột 10)
Giai đoạn cuối cùng ( chạy cho 2 phần tử ,và do đó thì chỉ có 1 bước trong giai đoạn này vì chỉ so sánh 2 phần tử còn lại trên cùng với nhau thôi )
1.So sánh 11 với 23 do 11<23 nên giữ nguyên ( cột 11 )

Oki
ta được dãy 11,23,42,65,74 ( cột cuối cùng trên hình vẽ trên )

function BubbleSort($sort_array,$column = 0,$reverse)

{

$lunghezza=count($sort_array);

for ($i = 0; $i < $lunghezza ; $i++){

for ($j = $i + 1; $j < $lunghezza ; $j++){

if($reverse){

if ($sort_array[$i][$column] < $sort_array[$j][$column]){

$tmp = $sort_array[$i];

$sort_array[$i] = $sort_array[$j];

$sort_array[$j] = $tmp;

}

}else{

if ($sort_array[$i][$column] > $sort_array[$j][$column]){

$tmp = $sort_array[$i];

$sort_array[$i] = $sort_array[$j];

$sort_array[$j] = $tmp;

}

}

}

}

return $sort_array;

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: