home

linear search

arrays

linked lists

hash tables

binary search

bubble sort

insertion sort

Bubble Sort

Bubble sort is the most basic way to sort a collection. It works by sequentially going through your array and comparing two values at a time, swapping them if necessary. It then repeats the process until no swaps are required.

Implementation

function sort(values) {
  var length = values.length - 1;
  do {
    var swapped = false;
    for(var i = 0; i < length; ++i) {
      if (values[i] > values[i+1]) {
        var temp = values[i];
        values[i] = values[i+1];
        values[i+1] = temp;
        swapped = true;
      }
    }
  }
  while(swapped == true)
};
sort([7, 4, 5, 2, 9, 1]);
//finished

Example

Click step to sort the array. (This is a very slow algorithm, you probably want to give up once you have a general feel for it.)

7
4
5
2
9
1
step

Characteristics

As you've no doubt seen, bubble sort requires a lot of steps in order to sort even a short collection. In fact, sorting this collection required almost as many steps as all of the steps from the previous sections combined. It takes a lot of iterations and comparison to small values to their final destination.

There are two interesting things to know about bubble sorts. First, large values are always sorted first. If you run through it again (if you are insane), you'll notice that the 9 then the 7 then the 5 and so on get sorted first. Knowing this, we could make the code slightly smarter and stop repeatedly iterating over already sorted values.

The other interesting thing about a bubble sort is that it only takes one iteration to detect that a collection is already sorted. That is, if the first iteration doesn't set swapped = true, no additional iterations are required. However, this is not a unique property of bubble sorts.

In The Real World

There is no scenario in which a bubble sort is the most efficient way to sort (and more often than not it's much less efficient). In fact, many very influential people feel that it shouldn't be taught given how useless (and horrible) an algorithm it is.

Personally, I think it's still worth understanding.

blog comments powered by Disqus