Bubble sorting

Our first topic concerns bubble sorting. It is likely to be the nuts and bolts of programming mastery, still having some potential for improvement, which we will also describe in the course of discussion.

The idea of the method is straightforward : assume we have an array of elements placed in random order, we will be sorting the elements in acsending order by looking at the pairs of adjacent element while moving from the first element to the last (or vice versa). If it happens that the elements of any pair are placed in reverse order, then we simply swap the elements and proceed to the next element for the further comparison.

The idea imitates a bubble moving from the bottom of the pond to the water surface, so that elements having lighter values are rising on top, while more heavy elements are sinking.

On completing the first iteration, we have the lightest element placed on top. We exclude this element and proceed to the next iteration. Once the second lightest element is rised to the second position, it is excluded from further considerations as well. The process is repeated untill we have all elements sorted e.g. in acsending order.

For example, consider the following array of integers placed vertically. First iteration yields 6 swaps as presented on below Figure before the lightest element having value of 1 is placed on top.



For the second iteration, do not take the 1st element in to account, as it is now the minimum found at previous iteration, and focus on sorting the elements marked with rectangle. The second iteration brings the following result.



Similarly, repeat the same process for the third iteration.



The 4th iteration can be considered as final, since the rest of elements in the rectangle are already sorted in acsending order. However, this may not be so evident for the computer, which will continue working for some more iterations. Or, is there any way to come to a stop at the 4th iteration?



Average number of comparisons and swapings is proven to show quadratic growth : Theta(n^2) , we, therefore, conclude that bubble sorting is slow and not efficient. However, its simplicity can be considered as the main advantage.

The code has been implemented in Java and, surely, can be available on request :) Please mail to maritimedomain@yahoo.com or leave a comment. Thanks