Explore BrainMass

# Bubblesort

### Implementation

Although it's origins aren't easily traced, bubblesort seems to have been around since the early 1960s1, often under other names like exchangesort and shuttlesort. The following pseudocode shows the basic, unchanged idea:

function bubbleSort(A)                              // A is an array to be sorted

n = length(A)

swapped = true

while swapped = true

swapped = false                           // swapped remains false if the algorithm visits                                                                                                                                       each element with no swaps

for i = 1 to n-1 inclusive

if A[i-1] > A[i]            // an element is bigger than the one after it

swap( A[i-1], A[i] )

swapped = true

Below is a visual representation of bubblesort performed on the unsorted array [6, 5, 3, 1, 8, 7, 2, 4]. The sorting shown in the graphic is also given in the form of a table to help trace the above code through the process.

For the table below, bold lettering indicates the numbers that were compared for a given value of i and * shows when a swap was not enacted. The variable 'swapped' remains true as long as at least 1 swap occured over that pass.

Bubblesort passes on an 8-digit array
i First Pass Second Pass Third Pass Fourth Pass Fifth Pass Sixth Pass
1  5, 6, 3, 1, 8, 7, 2, 4 3, 5, 1, 6, 7, 2, 4 1, 3, 5, 6, 2, 4* 1, 3, 5, 2, 4* 1, 3, 2, 4* 1, 2, 3
2  5, 3, 6, 1, 8, 7, 2, 4 3, 1, 5, 6, 7, 2, 4 1, 3, 5, 6, 2, 4* 1, 3, 5, 2, 4 1, 2, 3, 4 1, 2, 3
3  5, 3, 1, 6, 8, 7, 2, 4 3, 1, 5, 6, 7, 2, 4* 1, 3, 5, 6, 2, 4* 1, 3, 2, 5, 4 1, 2, 3, 4*
4  5, 3, 1, 6, 8, 7, 2, 4* 3, 1, 5, 6, 7, 2, 4* 1, 3, 5, 2, 6, 4 1, 3, 2, 4, 5
5  5, 3, 1, 6, 7, 8, 2, 4 3, 1, 5, 6, 2, 7, 4 1, 3, 5, 2, 4, 6
6  5, 3, 1, 6, 7, 2, 8, 4 3, 1, 5, 6, 2, 4, 7
7  5, 3, 1, 6, 7, 2, 4, 8
value of swapped true true true true true false

Notice that bigger numbers should never move left of where they began and smaller numbers never 'bubble' down to the large end of the list at the right.

For the more kinetic learners, this youtube video demonstrates the process through the medium of dance.

### Performance

You may have noticed from the above that bubblesort does take some steps to improve efficiency such as 'locking in' the last value at the end of each pass which is always guaranteed to be in it's rightful place and therefore not needed in any further comparisons or swapping. It is also designed so that the workload lessens with each pass, both in iterations and, generally, in the number of swaps required for the pass. However, as demonstrated in the sixth pass above, bubblesort does necessitate a 'useless' pass at the end once the list is fully sorted to ensure no further swaps are needed. In addition, the positioning of the elements plays a heavy role - for larger elements at the front ('rabbits'), it is a fairly swift ride to the back but small elements at the end of the list ('turtles') take a relatively long time to bubble up to the front.

In terms of order, the inner loop runs O(n) operations each time and is called O(n) times, leading to an overall O(n2) rate for bubblesort, much worse than quicksort or mergesort.

For these reasons, and others like them, bubblesort is rarely used in practice, though still widely taught. Donald Knuth writes in his famous book, The Art of Computer Programming, that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems"2.

The comb sort is an enhanced version of bubblesort that seeks to solve some of its problems with turtles, etc. and it runs at a speed comparable to quicksort3.

References:

1. Astrachan, O. (). Bubble Sort: An Archaeological Algorithmic Analysis. [ONLINE] Available at: http://www.cs.duke.edu/~ola/bubble/bubble.html. [Last Accessed 15/04/2014].

2Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106â€“110 of section 5.2.2: Sorting by Exchanging.

3. OJ (2008). Sorting Algorithms: The Comb Sort. [ONLINE] Available at: http://buffered.io/posts/sorting-algorithms-the-comb-sort/. [Last Accessed 15/04/2014].