Bubble sort

Background

Bubble sort is a stable comparison algorithm. It has an average complexity of O(n²), where 'n' is the number of elements to be sorted. It has a best case of O(n) when the input array is already sorted or nearly sorted. It is relatively easy to implement, but is too slow to be used in practice.

Play City Football Manager on your phone

Manage the football team of your city and make them champions!

If you need to sort a small amount of data and want to avoid the overhead and the complex code of the advanced algorithms, go for the insertion sort.
Despite being useless in practice, bubble sort offers some interesting problems and optimizations that are useful for studying purposes.

Algorithm

The bubble sort makes n - 1 passes through the array. Each pass starts from the beginning of the array and goes towards the end. Each step of the pass compares the current element to its right neighbor. If the compared elements are in the wrong order, they swap their places. This way the larger “bubbles” make their way to the top.

As usual, we will follow one example step by step: Sort the array: 7, 8, 0, 3, 5

Pass 1: 7, 8, 0, 3, 5
1. Compare 7 and 8. Are they in the wrong order? No. Continue with the next two numbers.
2. Compare 8 and 0. Are they in the wrong order? Yes. Swap them: 7, 0, 8, 3, 5
3. Compare 8 and 3 in the modified array. 8 > 3? -Yes => Swap: 7, 0, 3, 8, 5
4. Compare 8 and 5. 8 > 5? -Yes => Swap: 7, 0, 3, 5, 8
With this we reached the end of the array and the first pass is over. You may notice that the biggest number in the array 8 moved to the last position.

Pass 2: 7, 0, 3, 5, 8
1. 7 > 0? -Yes. => Swap: 0, 7, 3, 5, 8
2. 7 > 3? -Yes => Swap: 0, 3, 7, 5, 8
3. 7 > 5? -Yes => Swap: 0, 3, 5, 7, 8
4. 7 > 8? -No.
Pass two is over. Notice that the array is already sorted, but the algorithm needs to do two more passes to complete.

Pass 3: 0, 3, 5, 7, 8
1. 0 > 3? No
2. 3 > 5? No
3. 5 > 7? No
4. 7 > 8? No

Pass 4: 0, 3, 5, 7, 8
1. 0 > 3? No
2. 3 > 5? No
3. 5 > 7? No
4. 7 > 8? No

C implementation

void bubbleSortBasic(int array[], int size)
{
    int iterations = 0;
    int temp;
    for(int pass = 1; pass < size; ++pass)
    {
        for(int i = 0; i < size - 1; ++i)
        {
            ++iterations;
            if(array[i] > array[i+1])
            {
                temp = array[i+1];
                array[i+1] = array[i];
                array[i] = temp;
            }
        }
    }
    printf("Basic bubble sort finished, using %d iterations.\n", iterations);
}

Limit the number of comparisons in each pass

As you can see the algorithm does many unnecessary comparisons. Also it does many swaps of elements and this is a problem. It is a problem, because the swapping is generally slower operation than the comparison.

Can we improve the efficiency of the original bubble sort? Do you remember that after the first pass the biggest number took its final place? It is easy to notice that after the second pass the second greatest number will take its place, too. And after the third? Yes, this repeats for each pass. So what? Well, after each pass we know that we don't need to swap those elements. Therefore we can limit the range of every pass after the first. This will look like this:

Pass 1: 7, 8, 0, 3, 5
1. 7 > 8? No
2. 8 > 0? Yes => swap: 7, 0, 8, 3, 5
3. 8 > 3? Yes => swap: 7, 0, 3, 8, 5
4. 8 > 5? Yes => swap: 7, 0, 3, 5, 8

Pass 2: 7, 0, 3, 5, 8
1. 7 > 0? -Yes. => Swap: 0, 7, 3, 5, 8
2. 7 > 3? -Yes => Swap: 0, 3, 7, 5, 8
3. 7 > 5? -Yes => Swap: 0, 3, 5, 7, 8
We know 8 is in place so pass 2 has only 3 steps.

Pass 3: 0, 3, 5, 7, 8
1. 0 > 3? No
2. 3 > 5? No
We know that 7 and 8 are in sorted, so pass 3 is over.

Pass 4: 0, 3, 5, 7, 8
1. 0 > 3? No

Good optimization, don't you think? Yes, it is good, but for large arrays it is still too slow. Can we optimize the bubble sort even more? Sure..

We can remember the position of the last swap. If there were no swaps after that index, the rest of the array is already sorted and there is no need to check further in the next passes. This limits further the number of unnecessary comparisons.

Limit the number of passes

Looking at the last example we notice that the array was sorted in the second pass. The third and fourth passes did not do any swaps. Think for a minute how to optimize this...

To cut the unnecessary passes we add a boolean variable. This variable remembers if a swap was made in the last pass. If a swap was made, the array is still not sorted and the bubble sort continues with the next pass. If the variable is false, then it is “job done” and we save some CPU time. In the example above we will not do the 4th pass. In larger arrays this will save more steps.. eventually.

Pass 1: 7, 8, 0, 3, 5
1. 7 > 8? No
2. 8 > 0? Yes => swap: 7, 0, 8, 3, 5
3. 8 > 3? Yes => swap: 7, 0, 3, 8, 5
4. 8 > 5? Yes => swap: 7, 0, 3, 5, 8
Pass 2:
1. 7 > 0? Yes => swap: 0, 7, 3, 5, 8
2. 7 > 3? Yes => swap: 0, 3, 7, 5, 8
3. 7 > 5? Yes => swap: 0, 3, 5, 7, 8
Pass 3:
1. 0 > 3? No
2. 3 > 5? No

Bubble sort has rabbits and turtles - no kidding!

Let's consider the following two arrays: 6, 1, 2, 3, 4, 5 and 2, 3, 4, 5, 6, 1

Case 1: 6, 1, 2, 3, 4, 5
Pass1: 6, 1, 2, 3, 4, 5
1. 6 > 1? Yes => 1, 6, 2, 3, 4, 5
2. 6 > 2? Yes => 1, 2, 6, 3, 4, 5
3. 6 > 3? Yes => 1, 2, 3, 6, 4, 5
4. 6 > 4? Yes => 1, 2, 3, 4, 6, 5
5. 6 > 5? Yes => 1, 2, 3, 4, 5, 6

Pass2: 1, 2, 3, 4, 5, 6
1. 1 > 2? No
2. 2 > 3? No
3. 3 > 4? No
4. 4 > 5? No

No swaps were made, so the algorithm recognizes the sorted array and stops.

Case 2: 2, 3, 4, 5, 6, 1
Pass 1:
1. 2 > 3? No
2. 3 > 4? No
3. 4 > 5? No
4. 5 > 6? No
5. 6 > 1? Yes: 2, 3, 4, 5, 1, 6

Pass 2:
1. 2 > 3? No
2. 3 > 4? No
3. 4 > 5? No
4. 5 > 1? Yes: 2, 3, 4, 1, 5, 6

Pass 3:
1. 2 > 3? No
2. 3 > 4? No
3. 4 > 1? Yes: 2, 3, 1, 4, 5, 6

Pass 4:
1. 2 > 3? No
2. 3 > 1? Yes: 2, 1, 3, 4, 5, 6

Pass 5:
1. 2 > 1? Yes: 1, 2, 3, 4, 5, 6

Isn't this second case ridiculous? All that work to sort one number.

In case 1 the unsorted number “6” got to its place in one pass. This is rather quick for bubble sort. These big elements that find their place rather quickly are called “rabbits”.

In case 2, the unsorted number “1” needed 5 passes to reach that first spot. Such small elements, that are far from their place are called “turtles”. The turtles are a problem that can be solved using the modification called “Shaker sort”.

Shaker/Cocktail sort

Shaker sort is a modification of bubble sort. It alternates the directions of the passes. The first goes from the first element towards the last and pushes the biggest bubble to the top. The second pass goes from top to bottom and pushes the smallest element to first position. This solves the turtle problem.

Let's take a look at case 2 again using the shaker:

Case 2: 2, 3, 4, 5, 6, 1
Pass 1:
1. 2 > 3? No
2. 3 > 4? No
3. 4 > 5? No
4. 5 > 6? No
5. 6 > 1? Yes: 2, 3, 4, 5, 1, 6

Pass 2:
1. 1 < 5? Yes: 2, 3, 4, 1, 5, 6
2. 1 < 4? Yes: 2, 3, 1, 4, 5, 6
3. 1 < 3? Yes: 2, 1, 3, 4, 5, 6
4. 1 < 2? Yes: 1, 2, 3, 4, 5, 6

Pass 3:
1. 2 > 3? No
2. 3 > 4? No
3. 4 > 5? No

No swaps were made, so the array is sorted. In this case, two passes are saved.

The source code for all these optimizations is available on Git Hub. You can play around with the code to un-comment the various options. You can switch to manual input and give the algorithms different inputs to see how their performance changes.
As you can see from the following output, the Shaker Sort, using all optimizations performs best and the most simple implementation performs significantly worse.

Although we did some interesting improvements to the basic bubble sort it is still quite inefficient algorithm. Its average and worst complexity is still O(n²).
Its high number of swaps and comparisons make it worse than the other sorting algorithms with quadratic complexity (for ex. insertion sort, selection sort). Its optimized version is not easier to implement, so there is really no reason to use bubble sort in practice.

Want more creative stuff? Go to our algorithms page!