One of the most important aspects of bubble sort is that, for each iteration in the outer loop, there will be at least one swapping. If there is no swapping, then the list is already sorted. We can utilize this improvement in our pseudocode and redefine it like this:

procedure bubbleSort( A : list of sortable items ) 
   n = length(A) 
   for i = 1 to n inclusive do  
     swapped = false 
     for j = 1 to n-1 inclusive do 
       if A[j] > A[j+1] then 
         swap( A[j], A[j+1] ) 
         swapped = true 
       end if 
     end for 

     if swapped is false 
        break 
     end if 

   end for 
end procedure

As we can see that we now have a flag set for each iteration to be false, and we are expecting that, inside the inner iteration, the flag will be set to true. If the flag is still false after the inner loop is done, then we can break the loop so that we can mark the list as sorted. Here is the implementation of the improved version of the algorithm:

function bubbleSort(array $arr): array { 
    $len = count($arr); 

    for ($i = 0; $i < $len; $i++) { 
      $swapped = FALSE; 
      for ($j = 0; $j < $len - 1; $j++) { 
          if ($arr[$j] > $arr[$j + 1]) { 
            $tmp = $arr[$j + 1]; 
            $arr[$j + 1] = $arr[$j]; 
            $arr[$j] = $tmp; 
            $swapped = TRUE; 
          } 
      } 
         if(! $swapped) break; 
    }     
    return $arr; 
} 

Another observation is that, in the first iteration, the top item is placed to the right of the array. In the second loop, the second top item will be in the second to the right of the array. If we can visualize that after each iteration, the i^th cell has already stored the sorted items, there is no need to visit that index and do a comparison. As a result, we can reduce the outer iteration number from the inner iteration and reduce the comparisons by a good margin. Here is the pseudocode for the second improvement we are proposing:

procedure bubbleSort( A : list of sortable items ) 
   n = length(A) 
   for i = 1 to n inclusive do  
     swapped = false 
     for j = 1 to n-i-1 inclusive do 
       if A[j] > A[j+1] then 
         swap( A[j], A[j+1] ) 
         swapped = true 
       end if 
     end for 

     if swapped is false 
        break 
     end if 

   end for 
end procedure 

Now, let's implement the final improved version with PHP:

function bubbleSort(array $arr): array {
    $len = count($arr); 

    for ($i = 0; $i < $len; $i++) { 
      $swapped = FALSE; 
      for ($j = 0; $j < $len - $i - 1; $j++) { 
          if ($arr[$j] > $arr[$j + 1]) { 
            $tmp = $arr[$j + 1]; 
            $arr[$j + 1] = $arr[$j]; 
            $arr[$j] = $tmp; 
            $swapped = TRUE; 
          } 
      } 
      if(! $swapped) break; 
    }     
    return $arr; 
} 

If we look at the inner loop in the preceding code, the only difference is $j < $len - $i - 1; other parts are the same as the first improvement. So, basically, for our 20, 45, 93, 67, 10, 97, 52, 88, 33, 92 list, we can easily say that after the first iteration, the top number 97 will not be considered for second iteration comparison. The same goes for 93, which will not be considered for the third iteration, just like the following image:

If we look at the preceding image, the immediate question that strikes our mind is "Isn't 92 already sorted? Do we need to again compare all numbers and mark that 92 is already sorted in its place?" Yes, we are right. It is a valid question. This means that we can know, in which position we did the last swap in the inner loop; after that, the array is already sorted. So, we can set a bound for the next loop to go, until then, and only compare until the boundary we set. Here is the pseudocode for this:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   bound = n -1
   for i = 1 to n inclusive do
     swapped = false
     newbound = 0
     for j = 1 to bound inclusive do
       if A[j] > A[j+1] then
         swap( A[j], A[j+1] )
            swapped = true
            newbound = j
       end if
     end for

     bound = newbound

     if swapped is false
        break
     end if

   end for
end procedure

Here, we are setting the bound after completion of each inner loop and making sure we are not iterating unnecessarily. Here is the actual PHP code using the preceding pseudocode:

function bubbleSort(array $arr): array {
    $len = count($arr);
    $count = 0;
    $bound = $len-1;

    for ($i = 0; $i < $len; $i++) {
     $swapped = FALSE;
     $newBound = 0;
      for ($j = 0; $j < $bound; $j++) {
          $count++;
          if ($arr[$j] > $arr[$j + 1]) {
            $tmp = $arr[$j + 1];
            $arr[$j + 1] = $arr[$j];
            $arr[$j] = $tmp;
            $swapped = TRUE;
            $newBound = $j;

          }
      }
     $bound = $newBound;

     if(! $swapped) break;
    }
    echo $count."
";
    return $arr;
}

We have seen different variations of bubble sort implementations, but the output will always be the same: 10, 20, 33, 45, 52, 67, 88, 92, 93, 97. If this is the case, then how can we be sure that our improvements have actually had some impact on the algorithm? Here are some statistics on the number of comparisons for all four implementations for our initial list 20, 45, 93, 67, 10, 97, 52, 88, 33, 92:

As we can see, we have reduced the number of comparisons from 90 to 38 with our improvement. So, we can certainly boost up the algorithm with some improvements to reduce the number of comparisons required.