Detailed Explanation of Bubble Sorting of Bubble Sort Implementation Method of PHP Sorting Algorithm

In this paper, the implementation method of bubble sorting (Bubble Sort) of PHP sorting algorithm is described by an example. Share it for your reference, as follows:

Basic ideas:

Bubble sort is a kind of exchange sort. Its basic idea is to compare the keywords of adjacent records in pairs, and exchange them if they are in reverse order until there are no records in reverse order.

The simplest sort implementation:

Let's take a look at the sort methods that we often use before we learn all kinds of sort methods (at least I do....) :

// Type hints are used here ( type hint )  array Students who are unfamiliar or unaccustomed can be removed without affecting the calculation results 
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      // Put small keywords in front 
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

Strictly speaking, the above code is not a standard bubble sorting, because it does not satisfy the bubble sorting idea of "comparing adjacent records in pairs", it is just a simple exchange sorting. The idea is simply to start with the first keyword, compare every 1-bit keyword with all the keywords after it, and exchange it to get the smallest value. But this algorithm is very inefficient.

Bubble sorting algorithm:

It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. Visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted.

The name of this algorithm comes from the fact that the larger elements in the array will gradually "sink" to the back of the array after sorting once, while the smaller elements will gradually "float" to the front of the array, hence the name.

The bubble sorting algorithm works as follows: (from back to front)

1. Compare adjacent elements. If the first one is bigger than the second one, exchange them both.
2. Do the same for every 1 pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the maximum number.
3. Repeat the above steps for all elements except the last one.
4. Repeat the above steps for fewer and fewer elements at a time until there are no 1 pairs of numbers to compare.

Look at the text description. If you don't understand it, look at the code:

// Exchange method 
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
// Bubble sorting 
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    // Float small elements layer by layer from back to front 
    for($j = $length - 2;$j >= $i;$j --){
      // Compare adjacent records in pairs 
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

Improvement of Bubble Sorting Algorithm;

"Big Talk Data Structure" is really a good book, and it also introduces the improvement of bubble sorting algorithm. Here I will move its statement directly:

Can the bubble sorting algorithm above be optimized? The answer is yes. Imagine 1, if the sequence to be sorted is {2, 1, 3, 4, 5, 6, 7, 8, 9}, that is to say, everything is in normal order except the first and second keywords that need to be exchanged. When i = 0, 2 and 1 are exchanged, and the sequence is already ordered, but the algorithm still relentlessly executes i = 2 to 9 and j loop in each loop once. Although there is no exchange of data, a large number of comparisons after that are greatly redundant.
When i = 2, we have compared 9 with 8, 8 with 7, 3 with 2, and there is no data exchange, which shows that this sequence is orderly, and there is no need to continue the following judgment work (there will be no data exchange in the following work, and it is meaningless to do it again). In order to realize this idea, we need to improve the code under 1 and add a tag variable flag to realize the improvement of this 1 algorithm:

// Exchange method 
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/ Optimization of Bubble Sequencing ( If a 1 If there is no exchange of elements in the second loop, the whole array is already ordered )
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

The key to the code change is to add the judgment of whether flag is true in the for loop of i variable. After this improvement, the performance of bubble sorting has been improved, which can avoid the meaningless loop judgment under the condition that it has been ordered.

The total time complexity of bubbling algorithm is O (n ^ 2).

Bubble sort is a stable sort.

This article refers to "Dahua Data Structure", which is only recorded here, which is convenient for future reference. Don't spray it!

PS: Here we recommend another demonstration tool about sorting for your reference:

Online animation demonstrates insert/select/bubble/merge/hill/quick sort algorithm process tool:
http://tools.ofstack.com/aideddesign/paixu_ys

For more readers interested in PHP related contents, please check the special topics of this site: Summary of php Sorting Algorithm, Tutorial of PHP Data Structure and Algorithm, Summary of php Programming Algorithm, Summary of php String (string) Usage, Encyclopedia of PHP Array (Array) Operation Skills, Summary of PHP Common Traversal Algorithms and Skills and Summary of PHP Mathematical Operation Skills

I hope this article is helpful to everyone's PHP programming.