When I look at the following algorithm, I believe I understand how bubble sort works.
for i := 1 to n − 1
for j := 1 to n − i
if a[j] > a[j+1]
interchange a[j] and a[j+1]
However I am having a little tough time understanding statements like the following:
The only significant advantage that bubble sort has over most other algorithms, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm.
I see bubble sort having to make
n-1 passes, no matter what the sorted status of the collection is. Obviously I am missing something.