首页 > 代码库 > Bubble Sort

Bubble Sort

We have 8 numbers. Sort as ascend.

 

1st loop, we compare 7 times (for 8 numbers), and found the largest 8.

2nd loop, we compare 6 times (for 7 numbers), and found the largest 7.

...

 

1, 7, 8

2, 6, 7

3, 5, 6

4, 4, 5

5, 3, 4

6, 2, 3

7, 1, 2

 

In conclusion:

For sorting 8 numbers, we need an outer loop of 7 times, each time for finding a largest number; and an inner loop from comparing 7 times to comparing 1 time (as in the center column).

 

Implementation in PHP: 

 1 <?php 2 /* bubble sort:  3     1. operate directly on the input array (&), not on a copy 4     2. sort as ascend 5  6     a is array 7     m is length of a 8     n is times of sort 9     i/j is for-loop counter10     w is for value swap11 */12 function sortBubble(&$a){13     $m = count($a);14     $n = $m - 1;15     for($i=0; $i<$n; $i++){16         for($j=0; $j<$n-$i; $j++){17             if($a[$j] > $a[$j+1]){18                 $w = $a[$j];19                 $a[$j] = $a[$j+1];20                 $a[$j+1] = $w;21             }22             else{23                 // do nothing24             }25         }26         // see the results after each outer loop27         // echo implode(‘, ‘, $a).‘<br />‘;28     }29 }30 31 $arr = array(9, 5, 2, 7, 3);32 sortBubble($arr);33 echo implode(‘, ‘, $arr);34 35 // 2, 3, 5, 7, 937 ?>

 

Bubble Sort