Beginning Java Data Structures and Algorithms

Improving Bubble Sorting

There are two main techniques we can adopt to improve the performance of bubble sort. It's important to realize that although both of these strategies improve the overall performance of bubble sort in the average case; in the worst case, the algorithm still has the same poor runtime complexity of O(n²).

The first small enhancement we can make to the original bubble sort is to make use of the fact that a sorted "bubble" is building at the end of the list. With every pass we make, another item is added at the end portion of this bubble. This is the reason why (n - 1) passes are needed.

This is also shown in Figure 2.1. In this diagram, the items shown in the dotted circle are already sorted in the correct place: