Bubble Sort Algorithm (With Code)

In today’s world of continuous data generation, it is of utmost importance for all businesses to sort data linearly and attain relationships on the same. With different types of sorting algorithms present in the market today, the Bubble Sort algorithm is one of the most uncomplicated algorithms that you can use to sort data. 

 

In this article on the Bubble Sort algorithm, let us understand the following pointers:

• Understanding Bubble Sort Algorithm
• Bubble Sort Example
• Implementing Bubble Sort in C  
• Implementing Bubble Sort in Python
• Time & Space  Complexity of Bubble Sort
• Interview Questions on Bubble Sort

So, let us get started by understanding what the Bubble Sort algorithm is.

Bubble Sort Algorithm 

Bubble Sort is one of the simplest algorithms that compare adjacent elements and swap them if they are lesser/ greater based on the conditions mentioned. Here, each element is compared with all the other elements in the array till its final place is found, and no swap is required. This move of comparison of elements is known as a PASS.

But, have you ever wondered why this algorithm is known as – Bubble Sort, and where does its name originate?

Well, as metaphorically it sounds. Bubble sort gets its name from how bubbles tend to rise to water’s surface, similar to how the algorithm moves the elements towards a desired end to the list.

Algorithm:

Before we understand the algorithm, refer below to understand the steps involved:

In the 1st iteration:

• Compare the first and the second element of the array
• If the first element is greater than the second element, then swap the elements.
• Next, compare the second and third elements. If the second element is greater than the third element, swap them
• Repeat the steps until the array is sorted.

In the 2nd iteration:

Repeat the above steps for every iteration.

Note:  At the end of each iteration, the largest element of the unsorted array is placed at the end.

Now, that you have understood the workflow of Bubble Sort, refer below to understand the algorithm.

Here, lets us assume exarr is an array of n elements, and the swap function will swap the elements present in the array.

begin BubbleSortAlgo(exarr)
 
   for all elements of exarr
      if list[m] > list[m+1]
         swap(list[m], list[m+1])
      end if
   end for
 
   return exarr
 
end BubbleSortAlgo

Next, in this article, let us look into a simple example of the Bubble Sort Algorithm.

Bubble Sort Algorithm Example

To understand this sorting algorithm, let us consider a simple example and look at the step-by-step process.

Array considered: 17 34 25 49 09

Step 1: Start with comparing the first two elements, i.e., elements at the a[0], and a[1] position. In our example, our elements at a[1] > a[0]. So, it is already sorted.

Step 2: Next, the element at a[1] is compared with a[2]. Here we observe that a[1] > a[2],  which implies that these 2 values must be swapped.

So, the new array output will be – 17 25 34 49 09

Step 3: Now, consider this new array and compare elements at a[2] and a[3]. Here a[2] < a[3], so they are already at the sorted positions.

Step 4: Next, compare elements at a[3] and a[4]. Here a[3] > a[4]. So, we have to swap these values based on our condition.

Step 4.1: The output will be 17 25 34 09 49. Here clearly elements at a[2] > a[3]. So, we need to swap them again

Step 4.2: Post the swap, the output will be – 17 25 09 34 49. Here elements, at a[1] > a[2]. Based on the algorithm, it is clear that these elements are not sorted, and we have to swap them again.

Step 4.3: The new array post the swap will be 17 09 25 34 49. Here, you have to notice that, as when we implement a PASS, at-least one value moves towards the end of the array.

Step 4.4: Finally, we can see that elements at a[0] > a[1]. So, let us swap again and see the output.

Final Output: 09 17 25 34 49

Here, you can observe that you do not require a swap. Thus, it implies that the array is sorted. 

Bubble Sort in C  

C is a prevalent programming language in which you can implement Bubble Sort in a quick manner. Please refer to the below example bubble sort program in C.

//Bubble Sort
 
#include <stdio.h>
int main()
{
int arr[100], n, i, j, newarr; 
printf("Mention the number of elements in the array : ");
scanf("%d", &n); 
printf("Enter the %d elements in the array :\n",n); 
for(i = 0; i < n; i++)
scanf("%d", &arr[i]); 
for(i = 0 ; i < n - 1; i++)
{
for(j = 0 ; j < n-i-1; j++)
{
if(arr[j] > arr[j+1]) 
{
newarr=arr[j];
arr[j]=arr[j+1];
arr[j+1]=newarr;
}
}
} 
printf("\nSorted array : \n"); 
for(i = 0; i < n; i++)
printf("\t %d \t", arr[i]);
return 0;
}

Output:

Bubble Sort in Python

Bubble Sort can be implemented in the Python programming language, in the following way:

def BubbleSortAlgo(exarr):
    n = len(exarr)
    for i in range(n):
        for j in range(0, n-i-1):
            # Swap if the element at index - 1 is greater than element at index
            if exarr[j] > exarr[j+1] :
                exarr[j], exarr[j+1] = exarr[j+1], exarr[j]
 
# Take Users Input
n = int(input("Mention the number of elements in the array : "))
exarr = []
print("Enter the elements in the array")
for i in range(0, n):
    m = int(input())
    exarr.append(m)
 
# Display array before sorting
print("Array before Sorting :")
print(exarr)
 
BubbleSortAlgo(exarr)
#Display array after sorting
print ("Sorted array :")
for i in range(len(exarr)):
    print ("%d" %exarr[i])

Output:

Time & Space Complexity of Bubble Sort

Bubble Sort Algorithm has O(n^2) time complexity and is one of the slowest algorithms. We can further optimize Bubble Sort by using a flag variable that exits the loop once swapping is done. The best time complexity of Bubble Sort, which you can achieve is O(n). Here, please note that O(n) is only possible in the best-case scenario, i.e., when the array is already sorted.

Finally, let us take a look at the most asked questions on Bubble Sort.

Top Interview Questions on Bubble Sort Algorithm

Q1. What is the best & worst time complexity of Bubble Sort?

Ans. O(N) is the best complexity and the worst time complexity is O(N^2)

Q2. Can we recursively implement Bubble Sort?

Ans. Yes, we can recursively implement Bubble Sort. You have to execute one normal Bubble sort pass of the current sub-array to the correct position. Then, recur the same step for all elements except for the last element in the sub-array.

Q3. Is Bubble sort an inplace and a stable algorithm?

Ans. Yes, Bubble sort is both an inplace and a stable algorithm. 

Q4. Calculate the number of swappings required to sort the array 3, 29, 6, 9, 37, 2, 17 in ascending order.

Ans. A total of 10 swaps will be required to sort the array in ascending order – 2,3,6,9,17,29, 37

Q5. Mention 3 advantages of Bubble Sort over other sorting algorithms.

Ans.

1. The best-case time complexity is O(N) and is very easy to implement.
2. Comparatively generates faster output with respect to other algorithms if the array is already sorted.
3. The ability to detect whether the list is sorted efficiently or not.

With this, we end this article on Bubble Sort and how to implement it. We hope you found it informative. 

Explore More:

• Top Data Structure Interview Questions [DS and Algorthims]
• Tree Data Structures: Types, Properties, and Applications
• Understanding Data Structures in C: Types And Operations

If you have recently completed a professional course/certification, click here to submit a review.