0
$\begingroup$

When I look at the following algorithm, I believe I understand how bubble sort works.

procedure bubblesort
    for i := 1 to n − 1
        for j := 1 to n − i
            if a[j] > a[j+1]
            then
                interchange a[j] and a[j+1]
            endif
        endfor
    endfor
endprocedure

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

Probably that statement does not come from the same source where you got the pseudocode from. Another common way to define Bubblesort is the following:

procedure bubblesort
    sorted := false
    while not sorted
        sorted := true
        for j := 1 to n − i
            if a[j] > a[j+1] then
                swap a[j] and a[j+1]
                sorted := false
            endif
        endfor
    endwhile
endprocedure

As you can see there will be only one iteration of the outer loop when the collection is already sorted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.