Finnish version of this article.
Frankly, I don't understand why bubble sort is so widely used as the very first example of a sorting algorithm in programming courses around the world.
The usual argument is that bubble sort is the simplest sorting algorithm and the easiest to understand. However, I strongly disagree with this claim.
Bubble sort uses a rather ingenuous method for sorting, but understanding why it works can be a bit difficult for someone who has never programmed before nor has experience on algorithms. Certainly more difficult to understand than why eg. insertion sort works.
Insertion sort, on the other hand, is quite intuitive and easy to understand as an algorithm. It is much closer to how people intuitively sort items in real life, which makes it very natural. Bubble sort is very artificial and esoteric when you try to think of it in a real-life situation, and certainly not something you would do.
And what is more important, insertion sort is not only more intuitive and easier to understand, it is also a much more efficient O(n2) algorithm than bubble sort. I can't think of any example where bubble sort would be faster than insertion sort, whereas I can think of many simple examples where the opposite is true. Because of this insertion sort is a very viable algorithm to, for example, speedup quicksort, whereas bubble sort would be one of the worst possible choices.
In order to see how much easier it is to understand the idea behind insertion sort, I will try to describe both algorithms as simply as possible:
In both cases the task is to sort an array of items to increasing order:
The main difference between these two algorithms is that insertion sort handles one item at a time: It takes an item (starting from the second item forward) and puts it in place. This is how people would intuitively sort a set of item in real life: One item at a time.
Bubble sort, on the other hand, makes numerous passes through the array never concentrating on one single item, but just swapping items as it goes. There's a nice trick in this algorithm: After each pass the largest item will be located at the end of the array. However, understanding why this is so may not be quite obvious, especially not to someone new to programming.
A simple example demonstrates very well how intuitive insertion sort and how counter-intuitive bubble sort is: Take an array of 100 items which is otherwise already sorted, but the smallest item is at the end of the array. Then ask someone to sort it.
What would be the most logical way? Moving this last item to the beginning of the array, as in the insertion sort, or going through the array 99 times, each time making one swap at the end like bubble sort does? One immediately realizes that going through the array 99 times just to get the last item to the beginning feels a complete waste. Insertion sort goes through the array just 2 times in order to achieve the same goal.
Now, give this example to a beginner and show him the two sorting methods and ask him which one feels more intuitive and easier to understand.
The example given above shows another problem of bubble sort: Speed.
Although both algorithms are O(n2), bubble sort often wastes
enormous amounts of time for useless work. The sorted array but with the
smallest item at the end is a perfect example: While insertion sort will
make (n-1)*2 comparisons and n-1 swaps (for an
array of 1000 items it would be 1998 comparisons and 999 swaps), bubble
sort will make 1+2+3+...+(n-1) comparisons (499500 for an array
of 1000 items) and the same amount of swaps.
In other words, with an array of 1000 items bubble sort makes 497502 comparisons more than insertion sort to achieve the same goal. All those extra comparisons are completely useless (they don't achieve anything useful).
Insertion sort is very efficient for small arrays and arrays which are almost sorted. This is the reason why it is often used to speed up quicksort: Quicksort stops partitioning partitions smaller than a certain size (eg. 16 items) and then runs insertion sort. Insertion sort could be run on each individual subpartition, or it can be run once on the entire array when quicksort has finished. Because of the nature of insertion sort it doesn't make too much of a difference.
However, bubble sort would be horrendously inefficient to apply to the entire array like this. Even applying it to each subpartition separately would bring absolutely no benefit over insertion sort. It can only be slower.
Bubble sort is simply not useful for anything. I can't think of any example where it would be faster than insertion sort, and examples where it is even equally fast are rare. Bubble sort can only be slower than insertion sort.
Add to this the fact that bubble sort is a lot less intuitive and harder to understand. I really don't understand why it is taught as the first sorting algorithm.
Teaching bubble sort as some kind of "basic sorting algorithm" has real-life negative consequences. This is a real-life example: this is a piece of code in the gnu flex program:
/* We sort the states in sns so we * can compare it to oldsns quickly. * We use bubble because there probably * aren't very many states. */ bubble (sns, numstates);
There's absolutely no rational reason why bubble sort was used here instead of insertion sort. Bubble sort can only be slower, and it's not in any way easier to implement.
This is a real example of how teaching bubble sort as some kind of noteworthy algorithm causes real problems, which can be seen as low-quality code from people who should know better.