Bubble Sort Algorithm

Introduction

Consider a list with the elements – 5, 4, 3, 2 in it. You are asked to arrange these elements in both ascending and descending order.

In the above-given case, how are you going to perform this arrangement? Simple answer – by using a Sorting algorithm.

A sorting algorithm is a method of reorganizing the elements in a meaningful order. In the above-given example, we have implemented a sorting algorithm to get the desired results.

Ascending Sorting

Descending Sorting

There are multiple algorithms that can be used for sorting. And, in this article, we will discuss Bubble sort in the following order –

So let us now gear ourselves up to dive deeper and understand what bubble sort is.

What is Bubble Sort?

Bubble sort, also known as sinking sort, is the easiest sorting algorithm. It works on the idea of repeatedly comparing the adjacent elements, from left to right, and swapping them if they are out-of-order.

Two elements are said to be out of order if they do not follow the desired order. Recall the list which had elements 5, 3, 4, 2 in it. Here, 5 and 3 are out-of-order if we want to arrange the list in ascending order. Furthermore, 5 and 3 are in order if we want to sort the list in descending order.

In bubble sort, the repetition continues till the list we get the sorted list. Bubble compares all the elements in a list successively and sorts them based on their values.

Since it compares all the elements one by one, bubble sort is a slow algorithm and performs inefficiently in real-world scenarios. It is generally used for educational purposes or to determine if the sorted sorted given list is already sorted or not.

Working of Bubble Sort

Consider that we want to sort a list in ascending order, here are the steps that the algorithm would follow:

1. Start with the first element.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, then swap both the elements. If not, move to the next element.
4. Repeat steps 1 – 3 until we get the sorted list. To better understand bubble sort, recall the list that contains the elements 5, 3, 4, 2 initially.

The steps to sort this list would involve –

From the above-given diagram, we can infer the following conclusions about the bubble sort algorithm –

1. In bubble sort, to sort a list of size n, we need to perform n – 1 iterations. Notice we had 4 elements with us, and we got the sorted list in 3 passes. This is because each time we iterate over the list, an element gets sorted. This element is left in the next iteration of the loop. While we reach the (n – 1)th iteration, we are only left with one number. And, since a minimum of two numbers is required for comparison, that number can not be compared further.

2. In the first pass, the highest element (5 in this case) was bubbled out on the right side of the list. Similarly, after each iteration, the largest among the unsorted elements was placed at its position. This is the reason why this sorting algorithm is known as bubble sort.

3. In the second pass, we did not compare elements 4 and 5. This is because we know that 5 is already at its correct position, and comparing them would not make any difference. Same for 3 & 4 and 4 & 5 in the third pass. In each pass, comparison occurs up to the last unsorted element. This way we can reduce the number of comparisons.

4. Element 2 took a significant number of passes to arrange itself at its position in the sorted list. Thus, if any element of the list takes more passes, it is known as the turtle. Whereas element 5 took only one pass to reach its position, which is rare for bubble sort. Such elements are known as rabbits due to a low number of passes.

Imagine this. You are traveling on a straight road, and five cars are running at different speeds. For the sake of simplicity, let us assume that each of them is maintaining its respective speed.

What will happen if any car is moving faster than the one in front? Yes, the car at the back would overtake the one at the front. This way, the cars with the higher speed will occupy the position of the cars with the lower speed.

Now, following this, every car starts overtaking any car slower than itself. Eventually, the car with the highest speed will occupy the first position on the road, followed by the second-fastest car, and so on.

Notice how we used bubble sort to sort cars according to their speed. Here, with every overtake we were comparing the speeds of the cars, and if the car at the back was faster than the car at the front, they exchanged their positions, just like it is done in bubble sort.

Now that we have understood what bubble sort is, let us see how to implement a bubble sort algorithm via codes.

Bubble Sort Algorithm

We know that to sort a list of n elements using bubble sort, we need to perform n – 1 iterations. And for each iteration, we need to:

1. Run a loop over the entire list or array.
2. Compare the element at the index i with the element at i + 1.
3. If the element at i is greater than the element at i + 1, swap both the elements
4. Else, move to the next element.

Implementation of Bubble Sort

1. Bubble Sort Code in Java

2. Bubble Sort Code in Python

3. Bubble Sort Code in C

4. Bubble Sort Code in C++

Optimized Bubble Sort Algorithm

Imagine the case where the list is already sorted. For example, our input list contains 2, 3, 4, 5 instead of 5, 3, 4, 2.

In the above algorithm, the loop would still run to compare all the elements. It might cause complex issues like longer execution times.

To tackle this, we can do the following:

• Create a flag variable, called swapped.
• The value of the swap is set to true if, during any iteration, swapping was done.
• Else, the value of the swap is set to false.
• After an iteration, if the value of swapped is found to be false, it means the array is sorted, and no more comparisons are required.
• We then stop the execution.

It will help in reducing the number of comparisons, and hence the execution time of the algorithm.

Pseudocode

Notice the part where if the value of swapped is false, we stop the execution of the loop. It is done because we have already obtained a sorted list.

Now let us implement the above pseudocode in Java, Python, C, and C++.

Optimized Implementation of Bubble Sort

1. Optimized Bubble Sort Code in Java

2. Optimized Bubble Sort Code in Python

3. Optimized Bubble Sort Code in C

4. Optimized Bubble Sort Code in C++

Bubble Sort Complexity

1. Time Complexity

To better understand the time complexity, let us break the bubbleSort() function into the following parts:

Loop to iterate over the entire list Loop to iterate over the list to compare the next element. Let the number of elements in the list be n. Now, we know that for part 1, the loop would run for n times.

In part 1, each iteration of the loop would take constant time. Therefore, for part 1, we can say that time complexity would be O(n).

Part 2 is nested inside the loop that is run in part 1. Under this part, n comparisons are made that take constant time for execution. In other words, for each time part 1 is executed, part 2 will be executed n times. And if part 1 is executed for n number of times, part 2 would be executed for n * n number of times.

From this, we can say that the complexity of the selection sort algorithm is O($n ^ 2$).

Now let us discuss the time complexity in best, average, and the worst case.

• Worst Case: O($n ^ 2$). The worst case occurs when we want to sort a list in ascending order, but it is arranged in descending order.
• Average Case: O($n ^ 2$). The average case is when the list is arranged in a jumbled order.
• Best Case: O(n). The best case occurs when the list is already arranged in the desired order.

Therefore, the time complexity of a bubble sort algorithm is O ($n ^ 2$).

Recall the part where we had concluded that to sort a list of n elements, we need to perform n – 1 passes. And for each pass, we need to run a loop to iterate over the list. Now since the complexity of a for loop is O(n), and we are using two nested for loops, the time complexity of bubble sort can be explained as –

(n – 1) * (( n – 2) + (n – 3) + (n – 4) +….1 ), which would be equal to n * (n – 1)/2. And, in Big-Oh notation, this would be O($n^2$).

2. Space Complexity

• Simple Bubble Sort – The space complexity of the simple bubble sort algorithm is O(1). This is because we have used a fixed number of variables, and we do not need any extra memory space apart from the loop variables and auxiliary variable that includes temp. It means that we can sort an array containing a thousand elements even without using any extra variable

• Optimized Bubble Sort – The space complexity of the simple bubble sort algorithm is O(2). This is because we are using 2 extra variables – temp for swapping, and a flag variable called swapped.

Learn More

• Bubble Sort in C
• Bubble Sort in C++
• Bubble Sort in Java
• Bubble Sort in JavaScript

Exercise

• Binary search is one of the hottest topics in interview questions. Here is one such question.