Cyberithub

What is Bubble Sort Algorithm [Explained with examples]

Advertisements

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]

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.

What is Bubble Sort Algorithm [Explained with examples] 2

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

What is Bubble Sort Algorithm [Explained with examples] 3

  • So the final array after first round is:-

What is Bubble Sort Algorithm [Explained with examples] 4

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.

What is Bubble Sort Algorithm [Explained with examples] 5

  • Final array after second round is:-

What is Bubble Sort Algorithm [Explained with examples] 6

  • 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

What is Bubble Sort Algorithm [Explained with examples] 7

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

What is Bubble Sort Algorithm [Explained with examples] 8

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

What is Bubble Sort Algorithm [Explained with examples] 9

  • After first round the final array is:-

What is Bubble Sort Algorithm [Explained with examples] 10

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

What is Bubble Sort Algorithm [Explained with examples] 11

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

What is Bubble Sort Algorithm [Explained with examples] 12

  • 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

What is Bubble Sort Algorithm [Explained with examples] 13

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.

What is Bubble Sort Algorithm [Explained with examples] 14

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

What is Bubble Sort Algorithm [Explained with examples] 15

 

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 

What is Bubble Sort Algorithm [Explained with examples] 16

Output 

What is Bubble Sort Algorithm [Explained with examples] 17

 

b) C code snippet

What is Bubble Sort Algorithm [Explained with examples] 18

Output 

What is Bubble Sort Algorithm [Explained with examples] 19

 

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

What is Bubble Sort Algorithm [Explained with examples] 20

Output 

What is Bubble Sort Algorithm [Explained with examples] 21

 

b) C code snippet

What is Bubble Sort Algorithm [Explained with examples] 22

Output

What is Bubble Sort Algorithm [Explained with examples] 23

 

Performance 

  • As we are using two for loops, we can say that  the time complexity of the Bubble Sort Algorithm is O(n2).
  • The worst case occurs when the array is sorted in reverse order. The worst case complexity is O(n2).
  • The average case complexity is O(n2).
  • 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(n2) and space complexity is O(1).

Leave a Comment