Bubble Sort: Implementation and Analysis

Sorting is the lifeline of coding. We almost always want things in a natural order. An alphabetical order of a list of items is easier to comprehend. Going over your bank transaction history, ordered by date, is much better to analyze.

Today we have high-level, easy to read and write programming languages which usually have a built-in sort function. For instance, in C# you just need to call the Array.Sort() method, and C# would do the rest for you.

But understanding what is happening behind the scenes makes you a much better programmer. You can analyze how fast or slow your data is being sorted and what impact that algorithm is having on your application.

In this article we will look at the most basic sorting algorithm — Bubble sort. It has a fun name, and is easy to understand. We will first learn what bubble sort is and analyze the complexity of the algorithm. Then we will write some code in C#. We will also try to improve the performance of our code with the help of a boolean variable.

Bubble Sort — Definition

Bubble sort to sorting algorithms is like learning A-B-C-D to understand the English language! Let’s jump write into an example and learn the algorithm step by step. Consider the following array of numbers:

Start with the first two elements in the array and compare them. If the first element is greater than the second element, swap the elements.

Compare:

Swap:

Move on to the next two elements. Compare and Swap again as we did in the last step:

Compare:

Since these two elements are already sorted, we do not swap and move on to the next two elements

Compare:

Swap:

And finally compare and swap the last two elements:

Compare:

Swap:

We worked our way till the last index. And now our array looks like this:

I will pause here to point out that this is just one pass of the array. We went from index 0 to index 4, comparing and swapping along the way, and the outcome of this pass is that the highest element in the array (6) is at the last position. In other words, we have bubbled the highest element out to the last position — hence the name, bubble sort.

As you might have guessed, the algorithm does not stop here, as after the first pass, we have just brought one element to its correct position, and we still have the first four elements in wrong positions.

And so, we do another pass, but this time we go from index 0 to index 3 (as our last element has already been sorted). Let’s gray out the last element to make things clearer. Now that we have got a hang of how the comparison and swapping works, lets quickly go through the second pass:

After this pass, we have now brought the second highest element in our array to the correct position:

We are already down 2 passes, but our array is still not sorted. Let’s do another pass, but this time only till index 2, as the last two elements have been sorted:

After the third pass, our third highest element is in position:

We have one more pass to go, as the first two elements are still not sorted. This fourth pass will have only one comparison and swap operation:

and after this step, we have our sorted array:

Analysis and Complexity

Let’s stop here and note a few things that happened along the way:

1. We had 5 elements in our array, and we were able to sort the array in 4 passes. This means that for N elements, bubble sort will walk through the array N-1 times.
2. With every pass we were able to sort 1 element. When you look from this perspective, we can again conclude that for an array of N elements, we will need N-1 passes of the array.
3. In pass 1, we did 4 comparisons. In pass 2, we did 3 comparisons. In pass 3, we did 2 comparisons. In pass 4, we did 1 comparison. Thus, for an array of N elements, a bubble sort will do (N-1) + (N-2) + (N-3) +……+ 1 comparisons. In our example of 5 elements, we did 4+3+2+1 = 10 comparisons.
4. In pass 1, we did 3 swaps, In pass 2, we did 2 swaps, in pass 3, we did 1 swap and in pass 4 we did 1 swap again. This sums up to 3+2+1+1 = 7 swaps.
5. To summarize, to sort our array of 5 elements, we did 4 passes + 10 comparisons + 7 swaps = or a total of 21 steps or operations. We can also say that the total number of steps are close to (5)² (5 squared).
6. The worst case scenario would be when we have the array sorted in reverse order (descending). In that case we will have a swap with every comparison. In our above example, if all the elements were in descending order, then to sort our array we would have done 4 passes + 10 comparisons + 10 Swaps for a total of 24 operations. (again almost equal to 5²)

If you followed and understood all the 6 steps that we just did, then you just solved the complexity of a bubble sort! For an array with N elements, a bubble sort will take close to N² steps to fully sort the array. In other words, the complexity of a bubble sort is O(N²) or order of N squared. That means if we have an array of 6 elements, a bubble sort will take close to 36 steps, for 10 elements 100 steps, for 20 elements 400 steps. As you might have guessed, bubble sort is not a great choice when we have huge amounts of data. But by learning bubble sort, and by understanding why it gets in-efficient as the data increases, we can develop better and faster algorithms!

Implementation

Following is an implementation of bubble sort in C#:

• sortedIndex is initialized to point to the last element of the array. With every pass we will reduce the sortedIndex by 1
• Pass variable will track the number of passes of the array we do to fully sort the array
• ComparisonSteps variable will track the number of comparisons we do
• SwapSteps variable will track the number of swaps we do
• While (sortedIndex > 0) represents each pass of the array.
• The for loop covers all the comparisons and swaps in one pass

As you can see, we have initialized an array of 10 elements in our code, and the array is in descending order. This case represents a worst case scenario. On running the above code, we get the following:

The algorithm takes 9 passes, 45 comparison steps and 45 swap steps to give a total of 99 steps, which is close to 10². Thus giving a great example of the complexity of the algorithm.

A slightly better implementation

The implementation that we did earlier will take N-1 passes and compare every two elements along the way. Now consider a case when some elements of the array are already sorted. For example:

Here, the last three elements are already sorted, but according to the algorithm we will still need to compare all the elements.

We can slightly improve the implementation of our algorithm to first check if we already have a sorted array. We will declare a boolean variable “sorted” which will be set to false. During 1 pass, if we make a swap, we set the variable to true. Now, if we complete the pass, but we did not do any swap (because all elements were already sorted), the boolean variable “sorted” will still be set to false. This will indicate that the array has been sorted, and we can safely end the algorithm.

Our modified code will be as follows:

On running the above code on the array [1,0,2,5,6], we get the following output:

Note that we took only 1 pass and 1 swap step!! All because we checked along the way if the rest of the array is sorted, and exited the while loop when we no longer needed to go through each and every element.

Summary

In this article we did a deep dive to understand the bubble sort algorithm. It is a simple sorting algorithm which compares each and every element in an array, moving the greater element to the right with every pass.

The complexity of bubble sort is O(N²), and we did an in-depth analysis and implemented code to understand that. Bubble sort might not be a good algorithm to sort large amounts of data.

Feature Image: https://www.pexels.com/@padrinan