Improving bubble sort algorithm

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 ...

Get PHP 7 Data Structures and Algorithms now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.