64 SORTING ALGORITHMS
while swappedElements do
numberOfPairs = numberOfPairs - 1
swappedElements = false
for i = 1 to numberOfPairs do
if list[ i ] > list[ i + 1 ] then
Swap( list[i], list[i + 1] )
swappedElements = true
end if
end for
end while■ 3.2.1 Best-Case Analysis
We look quickly at the best case because the swappedElements flag might
give the wrong impression of how this algorithm functions. Consider what
will cause this algorithm to do the least amount of work. On the first pass, the
for loop must fully execute, and so this algorithm does at least N 1 com-
parisons. There are two possibilities that should be considered: There is at least
one swap or there are no swaps. In the first case, the swap will cause
swappedElements to be set to true, which will cause the while loop to
execute a second time, which will do another N 2 comparisons. In the sec-
ond case, because there are no swaps, swappedElements will still be false and
the algorithm will end.
So the best case is N 1 comparisons, and this occurs when there are no
swaps on the first pass. This means that the input data associated with the best
case would be when the data values are already in order.■ 3.2.2 Worst-Case Analysis
If the best case is when the input data starts in order, we might want to see if
having the input data in reverse order will lead us to the worst case. If the larg-
est value is first, it will be swapped with every other element down the list
until it is in the last position. At the start of the first pass, the second largest ele-
ment was in the second position, but you should see that the first comparison
on the first pass swapped it into the first position of the list. At the start of the
second pass, the second largest element is now in the first position, and it will
be swapped with every other element in the list until it is in the second to last
position. This gets repeated for every other element, and so the algorithm has