The method below has been taken from the book Data Structures & Algorithms by Robert Lafore. This method is used to bubble sort a given array. nElems is the number of elements in the array. In my opinion, there is a bug in this method, so instead of out > 1 it should be out > 0. Please help clarify.
public void bubbleSort() {
int out, in ;
for (out = nElems - 1; out > 1; out--) // outer loop (backward)
for ( in = 0; in < out; in ++) // inner loop (forward)
if (a[ in ] > a[ in +1]) // out of order?
swap( in , in +1); // swap them
}
private void swap(int one, int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
I tried to run the method, but I think it is wrong.
You wrote:
instead of
out > 1it should beout > 0.
That is a correct observation and correction.
Please help clarify.
The textbook version of the code will fail to sort an array correctly when the least value is at the very last index of the input array. That least value can "travel back" at most n-2 positions, by the repeated execution of the last swap in the inner loop, so that this least value ends up at the second position, while it needed to end up in the first position.
The smallest test case that fails would be an array with just 2 values, which are not in the right order, like for example {2, 1}. In that case the outer loop will not make any iterations, and thus no swap will be performed.
But any other input array that has its least value at the end, will not be sorted correctly, like for example {2, 3, 1} will be turned into {2, 1, 3}.
It is striking that the author continues with a section on invariants where they (correctly) claim:
the invariant is that the data items to the right of
outer[sic] are sorted. This remains true throughout running the algorithm.
This should have alerted them that at the end of the algorithm this invariant is only guaranteed for the data items at the right of index 1 -- as the value of outer is 1 when the loop exits on a non-empty input. That means this invariant rule gives no guarantee that involves the value at index 0.
In subsequent section on "efficiency of the Bubble Sort", they analyse that the number of comparisons is:
(N−1) + (N−2) + (N−3) + ... + 1
...but that last term (1) is a comparision that is not performed by their code. The last iteration of their outer loop will execute the inner loop twice, which is responsible for the previous term (2) in the above expression, leaving out the term 1.