BUBBLE SORT ALGORITHM

INTRODUCTION

In this tutorial, we will learn about the bubble sort algorithm. The bubble sort algorithm is the simplest sorting algorithm, which works on the repeated swapping of the elements according to the condition of the lexicographical order.

The bubble sort name itself suggests that the movement of the array elements is just like the movements of the air bubbles in water, likewise, the bubbles in the water rise up, similarly the array elements according to the intended order makes to the end.

In each iteration of the bubble sort, the present element is compared with the next element to it. If the current element is greater than the next element, then simply swap those two elements. This process is implemented on the whole array to obtain the sorted list of elements by using the bubble sort algorithm.

Let’s understand the working of the bubble sort with an example.

Let’s consider these are the elements of an array.

Arr= [23 ,56 ,32 ,78 ,12]

In the first pass, the whole array is traversed and checks whether the current element is greater than the next element. If it is true, then swapping of the elements occurs and the array would look like this after the first iteration.

23 56 32 78 12 
23 56 32 78 12 
23 32 56 78 12
23 32 56 78 12
23 32 56 12 78

In the second pass, we move to the second position, and the swapping of the adjacent elements according to the condition takes place like this.

23 32 56 12 78
23 32 56 12 78
23 32 56 12 78
23 32 12 56 78
23 32 12 56 78

The third pass of the elements looks like this.

23 32 12 56 78
23 32 12 56 78
23 12 32 56 78
23 12 32 56 78
23 12 32 56 78

The fourth pass of the list of elements is as follows

23 12 32 78 56
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78
12 23 32 56 78

The sorted array is 12 23 32 56 78

this is the working of the bubble sort algorithm. Now, let’s look at the algorithm for the bubble sort.

Now let’s look at the algorithm of the bubble sort.

ALGORITHM

Step 1: Start.
Step 2: If the current element is greater than the next element, swap those two elements.
Step 3: Continue the same process until the penultimate position of the list of elements.
Step 4: Stop.

Let’s look at the code implementing the bubble sort algorithm.

C++ Code:

#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[n];
    for(int i = 0 ; i<n ; i++) cin>>a[i];
    for(int i = 0 ; i<n-1 ; i++){
      for(int j = 0 ; j<n-i-1 ; j++){
        int k = j+1;
        if(a[j]>a[k]){
          int temp = a[j];
          a[j] = a[k];
          a[k] = temp; 
        } 
      }
    }
    for(int i = 0 ; i<n ; i++) cout<<a[i]<<" ";
}

JAVA code:  

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int n = s.nextInt();
      int a[];
      a = new int[n];
      for(int i = 0 ; i<n ; i++) a[i] = s.nextInt();
      for(int i = 0 ; i<n-1 ; i++){
      for(int j = 0 ; j<n-i-1 ; j++){
        int k = j+1;
        if(a[j]>a[k]){
          int temp = a[j];
          a[j] = a[k];
          a[k] = temp; 
        } 
      }
    }
      for(int i = 0 ; i<n ; i++) System.out.print(a[i]+" ");
  }
}

Python code

n = int(input())
a = []
for i in range(n):
  x = int(input())
  a.append(x)
for i in range(n-1):
  for j in range(n-i-1):
    k = j+1
    if a[j]>a[k]:
      temp = a[k]
      a[k] = a[j]
      a[j] = temp
for i in range(n):
  print(a[i],end=' ')
    

Input: 5
         23 56 32 78 12 

Output: 12 23 32 56 78


The time complexity of the code is O(n2) as here we use the nested for loops.
The space complexity of the code is O(1).

ADVANTAGES

• As the bubble sort algorithm is an in-place algorithm, there is no need for extra space.
• The bubble sort algorithm efficiently works over a small set of elements.
• In computer graphics, very minute errors can be detected easily using the bubble sort algorithm.

Now let’s look at the disadvantages of the bubble sort.

DISADVANTAGES

• The bubble sort algorithm is very less efficient likewise the selection sort as it uses nested loops which increases the time complexity of the code.
• Performance of the bubble sort algorithm is also based on the ordering of the elements in the list.
• The bubble sort algorithm is not so stable because multiple elements of the same value won’t possess their relative order after sorting.

CONCLUSION

That’s it from this tutorial. Hope you guys found It interesting. We have learned about the bubble sort algorithm, its implementation, and the advantages and disadvantages of the bubble sort algorithm and we have solved the bubble sort algorithm in different programming languages. Happy coding!