Please e-mail any questions, comments, or bugs to daniel.cer@cs.colorado.edu

<< Recent postings

Description: Code that sorts a list of floating point numbers using the well known, but often disparaged, bubble sort algorithm.

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).

Languages: C, C++, Java, Perl, Python, Ruby, Octave(/Matlab like), Scheme, and Bourne shell.

Source files:
BubbleSort.c [raw code], BubbleSort.cc [raw code], BubbleSort.java [raw code], BubbleSort.pl [raw code], BubbleSort.py [raw code], BubbleSort.rb [raw code], BubbleSort.m [raw code], BubbleSort.scm [raw code], BubbleSort.sh [raw code],

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.

Computers Blog Top Sites Blog Hub Blog Flux Directory