View Source: BubbleSort - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages

[BubbleSort] is the cannonical example of an inefficient sorting [Algorithm]. It works by moving through the array comparing each element with the next element and swapping them if they're in the wrong order. In each iteration, it moves the next largest element into the next last position, stopping one position earlier than previously. An example:

||After Iteration||||Element Nr.
|Outer|Inner|0|1|2|3
||^Initial state | D | B | C | A
| 1 | 1 | [[B] | [[D] | C | A
| 1 | 2 | B | [[C] | [[D] | A
| 1 | 3 | B | C | [[A] | [[__D__]
| 2 | 1 | [[B] | [[C] | A | D
| 2 | 2 | B | [[A] | [[__C__] | D
| 3 | 1 | [[A] | [[__B__] | C | D

The brackets denote the elements which were compared (and possibly swapped) during an iteration. Bold elements have reached their final position. As you can see, the next largest element falls into the next last position after each iteration.

A sample implementation might be

 int [] array;
 for(int i = array.length - 2 ; ; i--) {
    for(int j = 0; j < i ; i++)
       if (array[[j]>array[[j+1])
           swap(array[[j], array[[j+1]);
 }

It is obvious that, with ''n'' being the array's length, the inner loop will total ''(n / 2) * (n - 1)'' iterations - which is ''(n^2 - n) / 2''. Therefor, in [BigONotation], the complexity of BubbleSort is ''O(n^2)''. Clearly, its performance will degrade quickly as the array grows.

BubbleSort does have some good features, though:
# The weakness of BubbleSort is that it never shuffles non-adjacent elements - that's why it's so slow. But it also means that never degrades the order in its input, so you can take shortcuts if you know your list is nearly sorted. F.ex, if ''a'' unsorted elements have been prefixed to an otherwise sorted list then the outer loop can be aborted early, reducing the complexity to ''O(a n)''. For small values of ''a'', this will likely be less than the ''O(n log n)'' required f.ex by a full QuickSort run.
# [BubbleSort] can use fine-grained [Synchronisation] to sort a list while other threads or processes are updating it or changing it.

One page links to BubbleSort:

BigONotation

Last edited on Sunday, August 24, 2003 2:08:19 pm by AristotlePagaltzis

Edit PageHistory Diff Info LikePages