What is Bubble Sort?

Do not worry if you are a busy engineering student making your resumes and applications to get selected at your dream company, and you are left with data structures and algorithms!

Let us begin to cover them starting with sorting algorithms as they were made to deal with data and get it in the desired order. Through this article, we will discuss the Bubble Sort algorithm. Let’s make an attempt at recycling our bubble sort brain cells.

Imagine yourself being pushed by your PT teacher to arrange yourself in a heightwise line in your school days! What do you do if the line of the students is not arranged height-wise? Vacate your space to fit yourself according to your height. 

If this concept is applied technically, then what we come up with is bubble sort. The more prominent elements will bubble up to the rightmost side of the unsorted array, the largest being the last element in the unsorted array after completing a pass or cycle. This entire process is repeated till we get a sorted array or list. The bubble sort algorithm iterates through the unsorted list or array by comparing the values of adjacent elements, and if they are in the incorrect order, or not arranged in the ascending order it will swap them and move on to the next adjacent pair. 

Bubble sort is the simplest and foundation algorithm for other advanced sorting algorithms. Let’s have a look and see how this algorithm works.

How does bubble sort work? 

Let us consider an unsorted array of 5 elements:-

5

20

12

39

25

We will be using the bubble sort algorithm to sort this array. Firstly we will compare the first two elements and check which one is greater, and then we will arrange them in ascending order.

5

20

12

39

25

Here 5 < 20, so there is no need to swap.

Now we will be checking the following two elements, which are 20 and 12. We observe that 20>12, so we will arrange them in ascending order, 

5

20

12

39

25

5

12

20

39

25

Now, 5,12, and 20 are arranged in ascending order. So we will move to the next pair of elements which is 20 and 39, but since 20<39, no swap is required.

Hence, we now take the pair of 39 and 25. 39> 25, so we need a swap here.

5

20

12

39

25

5

12

20

25

39

 This is our sorted array in ascending order.

Let’s take a look at another example for a more precise understanding of the algorithm.

Source:-study tonight

Okay, folks, now it’s your turn to sort this array applying further iterations. And we will check how genius you are. So grab your pen and start working!

Solution:-

The image shows pass 1 of the series. Similarly, if we do further passes, we get the results as follows:-

Pass 2:- 1, 2, 4, 3, 5, 6

Pass 3:- 1, 2, 3, 4, 5, 6

This is our final sorted array:- 1, 2, 3, 4, 5, 6

I hope you have got your way out. If not, don’t worry, keep on reading the article to understand the whole procedure in detail.

A Glance View: Bubble Sort.

I have one handy thing that can be remembered while dealing with bubble sort: doing a single iteration over the entire array brings one element to its correct place in the array. It can also be remembered in the manner of n-1 iteration through the entire collection of elements, where n is the number of elements in the array while sorting. Learning bubble sort is essential to pave the way for higher-level concepts.

Here I have the pseudocode based on the steps I used earlier to do bubble sorting.

Pseudocode:

begin BubbleSort(arr)
for all elements of the arr
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Let’s have a quick overview of our algorithm and see how code works for bubble sort in different languages in the next section.

                                          Image source: makeagif

Bubble Sort: Examples 

Below I have written functions in different languages , which take the key parameter array as input to return the sorted array by using bubble sort algorithm. 

So hop in and move on to real codes in Python, Java and C++ languages:

Bubble Sort in Python:-

def bubble_sort(List):
for i in range(0, len(List) - 1):
swapped=false
for j in range(len(List) - 1):
if (List[j] > List[j + 1]):
temp = List[j]
List[j] = List[j + 1]
swapped=true
List[j + 1] = temp
if(!swapped):
break
return List

List = [11,12,28,19,32,2,4]

# Calling bubble sort function

print("The sorted list is: ", bubble_sort(List))
We get the output as:
The sorted list is:  [2, 4, 11, 12, 19, 28, 32]

Bubble Sort in C++:-

#include<iostream>
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
 }
 }
 if (swapped == false)
break;
}
}
void printArray(int arr[], int size)
(

    int i;

    for (i=0; i < size; i++)

    printf("n");

}

int main()

{

    int arr[] = {7,11,9,1,10,20,14,21,19,28};

    int n = sizeof(arr)/sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("List of sorted Element: \n");

    printArray(arr, n);

    return 0;

}

The output for the above code is:

List of sorted Elements:

1 7 9 10 11 14 19 20 21 28

Bubble Sort in Java:-

class Main
{
public
static void main(String[] args)
{
int pass = 0;
int[] a = {10, 12, 11, 19, 28, 2, 1, 4, 6, 8};
boolean swapped;
for (int i = 0; i < 10; i++)
swapped = false;
for (int j = 0; j < 10; j++)
{
if (a[i] < a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
swapped = true
}
}
if (swapped == false)
{
break;
}
pass++;
}
System.out.println("Your Sorted List is:");
for (int i = 0; i < 10; i++)
 {
System.out.print(a[i] + " ");
}
}
}

The output of the code:-

Your Sorted List is:

1 2 4 6 8 10 11 12 19 28

All these programs demonstrate that the algorithm goes through the entire list a number of times and each time it covers the list we call it a pass. It uses two loops: the inner loop compares adjacent elements and the outer loop performs iteration in every simulation pass. It uses a swapped variable for checking if the conditions for the sorting in the ascending order are satisfied, otherwise, it swaps the element and sets ‘swapped’ to true. If the swap is not required then it has ‘swapped’ set as false and we break from the outer loop.

In all the programs mentioned above, we used a given input array of 10 different elements, and we sorted it using bubble sort. We used for loops to pass through the pair of adjacent two parts to get a sorted array.

By the end of each loop, the largest element of the array gets shifted to the rightmost end, and this way, we get our sorted array.  Similarly, we can reverse the conditions to sort the array in reverse order(decreasing or non-increasing). 

Time Complexity:

In the above illustration of the codes, we make N-1 comparisons in the starting pass, where N is the number of elements in the array/list. And subsequently, we make N-2, N-3 in the second and third pass, respectively.

Therefore, the total of comparisons in a bubble sort is given by:

—> (N-1) + (N-2)+(N-3)….. + 1 = Sum of comparison

Which by the formula of summation gives us:

—> N(N-1)/2

So, the time complexity is O(n2).

Space complexity is O(1) as we used constant space.

For various other cases, we have time complexity as follows:-

• Worst-case time complexity- O(n2)
• Best Case time complexity- O(n)
• Average Case time complexity- O(n2)

Note: In the best case, the list/array will be already sorted.

Advantages/Disadvantages:

Bubble Sort is the simplest and easiest sorting technique algorithm, usually considered when we start with sorting basics. It acts as an alphabet for creating the sorting field. It is used in a wide range of things like computer graphics.

Let’s now dive into the merits and demerits of one of the simplest sorting algorithms:

Advantages of Bubble Sort:

1. Easiest and foundation algorithm of sorting.
2. Other than arrays, it requires very little memory space.
3. It has lesser lines of code.

Disadvantages of Bubble Sort:

1. It is highly inefficient for large data sets, as it can not manage data at significant critical levels based on pieces retained and takes more time to run than other sorting algorithms.

Although this sorting algorithm is not used frequently, it’s highly recommended to get its basics as it will be bridging the gulf for advanced algorithmic topics.

Frequently Asked Questions:

Key Takeaways:

Overall, Bubble Sort is a vital algorithm to understand. In this article, we discussed the critical insights of bubble sort. Being the simplest and the backbone algorithm for further advanced sorting, this article covered Bubble Sort in Python, Java, and C++ with its advantages, disadvantages, and various complexities. 

To learn more about this, you can check our other blogs on sorting algorithms.

Till then, stay tuned and happy learning!

By Ladali Jain