The Efficiency of Bubble Sort

The Bubble Sort algorithm contains two significant kinds of steps:

• Comparisons: two numbers are compared with one another to determine which is greater.

• Swaps: two numbers are swapped with one another to sort them.

Let’s start by determining how many comparisons take place in Bubble Sort.

Our example array has five elements. Looking back, you can see that in our first pass-through, we had to make four comparisons between sets of two numbers.

In our second pass-through, we only had to make three comparisons. This is because we didn’t have to compare the final two numbers, since we knew that the final number was in the correct spot due to the first pass-through.

In our third pass-through, we made two comparisons, and in our fourth pass-through, we made just one comparison.

So that’s:

4 + 3 + 2 + 1 = 10 comparisons.

To put this in a way that would hold true for arrays of all sizes, we’d say that for N elements, we make

(N - 1) + (N - 2) + (N - 3) … + 1 comparisons.

Now that we’ve analyzed the number of comparisons that take place in Bubble Sort, let’s analyze the swaps.

In a worst-case scenario, where the array is sorted in descending order (the exact opposite of what we want), we’d actually need a swap for each comparison. So we’d have 10 comparisons and 10 swaps in such a scenario for a grand total of 20 steps.

Let’s look at the big picture. With an array containing five values in reverse order, we make 4 + 3 + 2 + 1 = 10 comparisons. Along with the 10 comparisons, we also have 10 swaps, totaling 20 steps.

For such an array with 10 values, we get 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparisons, and another 45 swaps. That’s a total of 90 steps.

With an array containing 20 values, we’d have:

19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 190 comparisons, and approximately 190 swaps, for a total of 380 steps.

Notice the inefficiency here. As the number of elements increases, the number of steps grows exponentially. (In technical math terms, we’d actually say that it grows quadratically.) We can see this clearly in the following table:

If you look at the growth of steps as N increases, you’ll see that it’s growing by approximately N². Take a look at the following table:

Let’s express the time complexity of Bubble Sort with Big O notation. Remember, Big O always answers the key question: if there are N data elements, how many steps will the algorithm take?

Because for N values, Bubble Sort takes N² steps, in Big O we say that Bubble Sort has an efficiency of O(N²).

O(N²) is considered to be a relatively inefficient algorithm, since as the data increases, the steps increase dramatically. Look at this graph, which compares O(N²) against the faster O(N):

Note how O(N²) curves sharply upward in terms of number of steps as the data grows. Compare this with O(N), which plots along a simple, diagonal line.

One last note: O(N²) is also referred to as quadratic time.