It’s weird that bubble sort is the most famous sorting algorithm in practice since it is one of the worst approaches for data sorting. Why is bubble sort so famous? Perhaps because of its exotic name or because it is so easy to implement. First let’s take a look on its nature.

Bubble sort consists of comparing each pair of adjacent items. Then
one of those two items is considered smaller (lighter) and if the
lighter element is on the right side of its neighbour, they swap places.
Thus the lightest element bubbles to the surface and at the end of each
iteration it appears on the top. I’ll try to explain this simple
principle with some pictures.

### 1. Each two adjacent elements are compared

Here “2″ appears to be less than “4″, so it is considered lighter and
it continues to bubble to the surface (the front of the array).

### 2. Swap with heavier elements

On his way to the surface the currently lightest item meets a heavier element. Then they swap places.

### 3. Move forward and swap with each heavier item

The problem with bubble sort is that you may have to swap a lot of elements.

### 4. If there is a lighter element, then this item begins to bubble to the surface

If the currently lightest element meets another item that is lighter,
then the newest currently lightest element starts to bubble to the top.

### 5. Finally the lightest element is on its place

At the end of each iteration we can be sure that the lightest element is on the right place – at the beginning of the list.

The problem is that this algorithm needs a tremendous number of comaprisons and as we know already this can be slow.

We can easily see how ineffective bubble sort is. Now the question
remains – why is it so famous? Maybe indeed the answer lies in the
simplicity of its implementation. Let’s see how to implement bubble
sort.

## Implementation

Implementing bubble sort is easy. The question is how easy? Well,
obviously after understanding the principles of this algorithm every
developer, even a beginner, can implement it. Here’s a PHP
implementation of bubble sort.

$input = array(6, 5, 3, 1, 8, 7, 2, 4); function bubble_sort($arr) { $length = count($arr); for ($i = 0; $i < $length; $i++) { for ($j = $length-1; $j > $i; $j--) { if ($arr[$j] < $arr[$j-1]) { $t = $arr[$j]; $arr[$j] = $arr[$j-1]; $arr[$j-1] = $t; } } } return $arr; } // 1, 2, 3, 4, 5, 6, 7, 8 $output = bubble_sort($input);

Clearly the implementation consists of few lines of code and two nested loops.

## Complexity: Where’s Bubble Sort Compared to Other Sorting Algorithms

Compared to other sorting algorithm, bubble sort is really slow. Indeed the complexity of this algoritm is O(n^{2}) which can’t be worse. It’s weird that the most well known sorting algorithm is the slowest one.

Even for small values of n, the number of comparisons and swaps can be tremendous.

Another problem is that most of the languages (libraries) have
built-in sorting functions, that they don’t make use of bubble sort and
are faster for sure. So why a developer should implement bubble sort at
all?

## Application: 3 Cool Reasons To Use Bubble Sort

We saw that bubble sort is slow and ineffective, yet it is used in
practice. Why? Is there any reason to use this slow, ineffective
algorithm with weird name? Yes and here are some of them that might be
helpful for any developer.

### 1. It is easy to implement

Definitely bubble sort is easier to implement than other “complex”
sorting algorithms as quicksort. Bubble sort is easy to remember and
easy to code and that’s great instead of learning and remembering tons
of code.

### 2. Because the library can’t help

Let’s say you work with JavaScript. Great, there you get array.sort()
which can help for this: [3, 1, 2].sort(). But what would happen if
you’d rather like to sort more “complex” structures like … some DOM
nodes. Here we have three LI nodes and we want to sort them in some
order. Obviously you can’t compare them with the “<" operator, so
we've to come up with some custom solution.

<a href="#">Click here to sort the list</a> <li>node 3</li> <li>node 1</li> <li>node 2</li>

Here sort() can’t help us and we’ve to code our own function. However
we have only few elements (three in our case). Why not using bubble
sort?

### 3. The list is almost sorted

One of the problems with bubble sort is that it consists of too much
swapping, but what if we know that the list is almost sorted?

// almost sorted [1, 2, 4, 3, 5]

We have to swap only 3 with 4.

Note that in the best case bubble sort’s complexity is O(n) – faster than quicksort’s best case!

Source: http://www.stoimen.com/blog/2012/02/20/computer-algorithms-bubble-sort/

## Comments

## Oliver Weiler replied on Wed, 2012/02/22 - 5:52am

## Stoimen Popov replied on Wed, 2012/02/22 - 7:15am

## Kookee Gacho replied on Mon, 2012/06/18 - 5:10am

## Kookee Gacho replied on Mon, 2012/06/25 - 7:38am