Bubble Sort

Bubble Sort

Bubble Sort is an algorithm that sorts an array from the lowest value to the highest value.

Run the simulation to see how it looks like when the Bubble Sort algorithm sorts an array of values. Each value in the array is represented by a column.

The word 'Bubble' comes from how this algorithm works, it makes the highest values 'bubble up'.

Manual Run Through

Before we implement the Bubble Sort algorithm in a programming language, let's manually run through a short array only one time, just to get the idea.

Step 1: We start with an unsorted array.

Step 2: We look at the two first values. Does the lowest value come first? Yes, so we don't need to swap them.

Step 3: Take one step forward and look at values 12 and 9. Does the lowest value come first? No.

Step 4: So we need to swap them so that 9 comes first.

Step 5: Taking one step forward, looking at 12 and 11.

Step 6: We must swap so that 11 comes before 12.

Step 7: Looking at 12 and 3, do we need to swap them? Yes.

Step 8: Swapping 12 and 3 so that 3 comes first.

Repeat until no more swaps are needed and you will get a sorted array:

Implement Bubble Sort in Python

To implement the Bubble Sort algorithm in Python, we need:

• An array with values to sort.
• An inner loop that goes through the array and swaps values if the first value is higher than the next value. This loop must loop through one less value each time it runs.
• An outer loop that controls how many times the inner loop must run. For an array with n values, this outer loop must run n-1 times.

The resulting code looks like this:

Bubble Sort Improvement

The Bubble Sort algorithm can be improved a little bit more.

Imagine that the array is almost sorted already, with the lowest numbers at the start, like this for example:

In this case, the array will be sorted after the first run, but the Bubble Sort algorithm will continue to run, without swapping elements, and that is not necessary.

If the algorithm goes through the array one time without swapping any values, the array must be finished sorted, and we can stop the algorithm, like this:

Bubble Sort Time Complexity

The Bubble Sort algorithm loops through every value in the array, comparing it to the value next to it. So for an array of \(n\) values, there must be \(n\) such comparisons in one loop.

And after one loop, the array is looped through again and again \(n\) times.

This means there are \(n \cdot n\) comparisons done in total, so the time complexity for Bubble Sort is: \( O(n^2) \)

The graph describing the Bubble Sort time complexity looks like this:

As you can see, the run time increases really fast when the size of the array is increased.

Luckily there are sorting algorithms that are faster than this, like Quicksort, that we will look at later.