I've been working on web based projects built mainly with PHP and JavaScript, where I mostly use Zend Framework and jQuery. I am interested in any webpage optimizations techniques - for a faster web! Stoimen is a DZone MVB and is not an employee of DZone and has posted 96 posts at DZone. You can read more from them at their website. View Full User Profile

Algorithm of the Week: Bubble Sort

02.21.2012
| 29305 views |
  • submit to reddit

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 comparedIn bubble sort we've to compare each two adjacent elements


In bubble sort we've to compare each two adjacent elements

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

If heavier elements appear on the way we should swap them


If heavier elements appear on the way we should swap them

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

Swapping is slow and that is the main reason not to use bubble sort


Swapping is slow and that is the main reason not to use bubble sort

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

We can be sure that on each step the algorithm bubbles the lightest element so far


We can be sure that on each step the algorithm bubbles the lightest element so far

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

Finally the list begins to look sorted


Finally the list begins to look sorted

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(n2) which can’t be worse. It’s weird that the most well known sorting algorithm is the slowest one.

Bubble sort compared to quicksort, merge sort and heapsort in the average case


Bubble sort compared to quicksort, merge sort and heapsort in the average case

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

stats


Bubble sort is three times slower than quicksort even for n = 100, but it's easier to impelemnt

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/

Published at DZone with permission of Stoimen Popov, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

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

Really, stop teaching BubbleSort. Instead, focus on InsertionSort, which performs better in almost all situations, is faster than any sort for very small datasets and can be used e.g. in MergeSort to optimize it for small datasets. And, on top of that, I'd say it's as easy (if not easier) to grasp than BubbleSort.

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

Actually both bubble sort and insertion sort have the same complexity - O(n*n) in the average case and O(n) in the best case. Which of them both are easier to implement, well it depends on the developer, but for sure both are quite easy.

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

The concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a small set of axioms and rules. In logic, the time that an algorithm requires to complete cannot be measured, as it is not apparently related with our customary physical dimension. -Arthur van der Vant

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

While there is no generally accepted formal definition of "algorithm," an informal definition could be "a set of rules that precisely defines a sequence of operations." -Marla Ahlgrimm

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.