This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.
The algorithm operates by iterating over a list and swapping, in place, every pair of adjacent items that are not in the correct order. After iterating through the list once, the list's values will not necessarily be in the correct sort order. Rather, for a list of N items, N passes over the list maybe necessary to ensure that all of the values are property sorted. However, after the i-th pass through the list, the last i values in it will be in their correct and final locations. As such, each pass only really needs to operate over N-i items. Additionally, if during any pass, no swaps are necessary, then the list is already sorted and the algorithm can terminate early.
If implemented with such early stopping, as seen in the code samples below, and if bubble sort is given an already sorted listed, then only one pass through the list, consisting of N-1 iterations, will be required [Note: each pass through the list that operates over n items, will only require n-1 iterations since there are only n-1 adjacent locations in a sequence of n items]. This being the best case for the algorithm. However, if the algorithm must make all N passes through the list, ((N-1)N)/2 iterations will be needed. As such, the algorithm has a time complexicty of O(n2).
![[Valid RSS]](/renma/images/valid-rss.png "Validate my RSS feed")
