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