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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.