Bubble Sort

To achieve a bubble sort you step through the unsorted list, compare each pair of adjacent items and swap them if they are in the wrong order. This puts the last item into its final position. You then repeat the pass through the list until no swaps are needed. Sorting methods such as quicksort that can exchange values that are far apart in the unsorted list are much faster than bubble sort for large random lists.

Bubble sort is used widely in tutorials and websites as an introduction to sorting even though it is generally not efficient. (It is quicker than many methods, however, if the list is nearly sorted already). An appeal of bubble sort is its simplicity. It also serves to highlight the advantages of other methods!

We demonstrate the bubble sort in programs ListDemo, LinkedListDemo and BubbleSortDemo.

The efficiency of the bubble sort can be improved slightly, for example by making alternate passes through the data in opposite directions. It then becomes the appealingly named cocktail-shaker sort.

Programming - a skill for life!

Bubble sort, insertion sort, tree sort and quicksort