In the last post we looked at how to really understand Selection Sort by solving it on paper, one step at a time. We’ll take the same approach for Bubble Sort.

While bubble sort is not one of the algorithms you’ll likely get asked in a FAANG interview, it’s still a pretty fundamental sorting algorithm to know. Let’s get started.

Strategy for Bubble Sort

Given an unsorted array of integers, we want to sort them in ascending order. The array under consideration is shown below:

Unsorted array to be sorted with Bubble sort

Here is the strategy:

1. Iterate through the unsorted array comparing each pair adjacent elements.
2. If the adjacent elements are in the wrong order, swap them
3. Repeat steps 1 and 2 from the beginning of the array till the entire array is sorted

The above steps results in smaller elements bubbling to the beginning of the array.

At the end of the first iteration, the smallest element is in the right position , at the end of the second iteration the second smallest element will be in the right position etc. For an array of N elements , we’ll need a maximum of N iterations to get all the elements in the correct position.

Note: There is a little trick we can do to require less than N iterations if the array is mostly sorted. The trick is to keep a flag that tracks whether we swapped any element in the last iteration. If no elements were swapped, that means the array has already been sorted – so we can just stop the iterations early. This little trick makes Bubble Sort an adaptive sorting algorithm.

Visualize the algorithm on paper

Again, this is the most important part to understand in this article. It’s not the code or the analysis, but solving it on paper. If you can do this, everything else will be a piece of cake.

Bubble Sort 1

At the end of the first iteration, 10 had bubbled up to the correct (last) position in the array.

Now we’re ready for the next pass. Go to the beginning of the array and start the process again.

Bubble Sort 2

We’re now done with the second iteration. 7 has bubbled up to the correct position. Note that now the last four elements in the array are sorted. So we’ll need less passes than the worst case scenario. This is because 4 elements are sorted in 2 passes and each pass of bubble sort ensures the next biggest element is bubbled up to the correct position.

okay, ready for the next pass ? Start comparing elements from the beginning.

Bubble Sort 3

This is the end of the third iteration. Note that the last 5 elements are now sorted.

To finish this up, go back to the first two elements and start the next iteration of compare and swap. Continue iterating till the whole array is sorted.

Note: I’d highly recommend that you try this on paper – this’ll help you really understand the algorithm and remember it in the long term.

Implementing Bubble Sort in C#

namespace Sorting
{
    class BubbleSort
    {
        public static bool debug = false;

        public static void Sort(int[] inputArr)
        {
            for(int i=0; i< inputArr.Length; i++)
            {
                bool swapped = false;

                for(int j=0; j < inputArr.Length -1; j++)
                {
                    if(inputArr[j] > inputArr[j+1])
                    {
                        Utilities.Swap(inputArr, j, j + 1);
                        swapped = true;

                        if (debug)
                        {
                            Utilities.PrintArray(inputArr);
                        }
                    }
                }

                if(!swapped)
                {
                    break;
                }
            }
        }
    }
}

Analysis of Bubble Sort

When to use and when to avoid Bubble Sort ?

Use bubble sort in the following scenarios:

1. When the array is partially sorted – since bubble sort is adaptive
2. When we have memory usage constraints
3. When a simple sorting implementation is desired
4. When the array to be sorted is relatively small

Avoid using bubble sort when:

1. The array to be sorted has a large number of elements
2. The array is completely  unsorted
3. You want a faster run time and memory is not a concern.