In this article, we will see what is Bubble Sort Algorithm and how it works. Why is sorting necessary? It is necessary because we can locate an element in a sorted list more quickly and efficiently, something that will be very difficult to do in a list where elements are in random order. There are many sorting algorithms developed over the time to sort the elements is much more efficient way, each of them having their own pros and cons. While we have discussed some of them in our earlier articles, here we will look into one such sorting algorithm called Bubble Sort.

What is Bubble Sort Algorithm [Explained with examples]

Also Read: What is Selection Sort Algorithm [Explained with Practical example]

Bubble sort is a very simple and easy to implement sorting algorithm. In the Bubble sort algorithm, elements tend to move up in the correct order same as the bubbles rising to the surface and that is how the bubble sort algorithm gets its name. Logic starts with comparison of two adjacent elements and if the left element is greater than the right element, they swap their positions and comparison proceeds till the end of the array. It is not ideal for large datasets as it has high time complexity.

 

Working of Bubble Sort Algorithm

The main idea is to compare adjacent elements, if the left element is greater than the right element, then we will swap.

Example 1

Let us take a small example with only three elements , for basic understanding of how this bubble sort algorithms work

arr[ ]= {11,8,7}

As we can observe the elements are already placed in non-increasing order, we will sort them in increasing order using the bubble sort algorithm. As there are three elements, there would be ( 3 - 1 ) i.e. 2 rounds of comparison. In the first round the greatest element will find its correct position which would be extreme right. After each round one element will occupy its correct position.

a) First Round

• We will first compare 11 and 8 , as 11 is greater than 8 so 11 and 8 will swap their positions.

• Now we will compare 11 and 7, since 11 is greater than 7 we will swap them:-

• So the final array after first round is:-

b) Second Round

• As 11 is fixed at this position. We will compare 8 and 7 , 8 is greater than 7 so we will swap them.

• Final array after second round is:-

• And this is our sorted array.

 

Example 2

Let us take one more small example , we have a list of numbers stored in an array

                                             arr[ ] = {23 , 46 , 19 , 59 }

There are 4 elements so 3 rounds of comparison will be done.

a) First Round

• In the first round the greatest element among these 4 elements will move to the extreme right.
• We will first compare 23 and 46 as 46 is greater than 23, so no swapping will take place

• Now we will compare 46 and 19 since 46 is greater than 19 , swapping will take place

• Now again we will compare 46 and 59 , since 59 is greater than 46 that is why no swapping will take place.

• After first round the final array is:-

b) Second Round

• Since 59 is placed at its right position , it is fixed now,  we have only 3 elements to has to be sorted

• Now we will compare 23 and 19 , 23 is greater than 19 so swapping will take place.

• Then we will compare 23 and 46, as 23 is smaller than 46 , that is why no swapping will happen.
• We will not compare 46 with 59 as 59 is already at its correct position.
• After second round final array is

c) Third Round

• 46 and 59 are at their correct positions , there are only two elements which have to be sorted, that is 19 and 23.
• Now compare 19 and 23 , as 23 is greater than 19 , no swapping will take place.

• And further no comparison will take place as each element occupies their correct position.
• After 3 rounds we finally got our sorted array.

 

Pseudocode 

bubbleSort( arr[n] )                     //n is the number of elements in array
    for i=0 to  n-1
         for j=i to n
              if arr[i]>arr[j]
                   swap arr[i] and arr[j]

 

 

Implementation in C/C++

Here I am using Visual Studio Code to write below C/C++ program and the MinGW-w64 compiler is used for compiling the code.

a) C++ code snippet 

Output 

 

b) C code snippet

Output 

 

Bubble Sort Algorithm for sorting in non-increasing order

The algorithm will remain the same, but now we want the greatest element in the beginning so we will swap elements only if the right element is greater than the left element. To implement this in code we will change arr[i] > arr[j] to arr[i] < arr[j] else everything will remain the same.

 

Implementation for Non-increasing order

Similar to above, here also I am using Visual Studio Code to write below C/C++ program and the MinGW-w64 compiler is used for compiling the code.

a) C++ code snippet

Output 

 

b) C code snippet

Output

 

Performance 

• As we are using two for loops, we can say that  the time complexity of the Bubble Sort Algorithm is O(n²).
• The worst case occurs when the array is sorted in reverse order. The worst case complexity is O(n²).
• The average case complexity is O(n²).
• The best case occurs when the array is already sorted. The best case time complexity is O(n).
• As we are not using any extra space the space complexity of the Bubble Sort algorithm is O(1).

 

Advantages 

• Simple and easy to implement
• It is Stable algorithm
• Short Code
• Storage space required is minimal

 

Disadvantages 

• Not ideal for large datasets
• Time complexity is very high
• Not suitable for real life applications

 

Conclusion

It is a simple algorithm of a few lines of code which includes mainly two for loops. We repeatedly compare adjacent elements and swap if they are not in the correct order. The time complexity of the Bubble Sort Algorithm is very high, that is O(n²) and space complexity is O(1).