The bubble sort is one of the simplest and most popular sorting algorithms.

The bubble sort works by repeatedly swapping adjacent elements until they are no longer in the intended order.

It is called bubble sort because it mimics the movement of bubbles in water.

A bubble in the water rises to the surface each time; similarly, elements in the bubble sort are moved to the end in each iteration.

Although simple to use, bubble sort is mainly used as an educational tool because its performance is poor in the real world.

It is not suitable for large data sets.

The average and worst-case complexity of Bubble sort is O (n2), where n is several items.

Time Complexity

Best Case O(1): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case O(n): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O(n): This occurs when the array elements need to be sorted in reverse order. In other words, suppose you have to sort an array in ascending order, but its elements are arranged in descending order.

Space Complexity

A bubble sort required extra variables for swapping. Hence, the space complexity of bubble sorting is O(1).

The space complexity of optimized bubble sort is O(2). This is because two extra variables are required in the optimized bubble sort.

Example:

C Program

#include <stdio.h>    

//function to print array elements  
void print(int a[], int n) {  
    int i;  
    for(i = 0; i < n; i++)    
        printf("%d ",a[i]); 
}  

// function to implement bubble sort  
void bubble_sort(int a[], int n) {  
   int i, j, temp;  
   for(i = 0; i < n; i++) {    
      for(j = i+1; j < n; j++) {    
            if(a[j] < a[i]) {    
                temp = a[i];    
                a[i] = a[j];    
                a[j] = temp;     
            }     
        }     
    }     
}  

void main() {    
    int i, j, temp;     
    int a[6] = { 50, 20, 32, 13, 30, 18};     
    int n = sizeof(a) / sizeof(a[0]);   
    printf("Before sorting array elements are - n");  
    print(a, n);  
    
    bubble_sort(a, n);  
    printf("nAfter sorting array elements are - n");    
    print(a, n);  
} 

Java Program

public class BubbleSort {  
    //function to print array elements 
    static void print (int a[]) {  
        int n = a.length;  
        for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");      
    }  
    
    // function to implement bubble sort  
    static void bubbleSort(int a[]) {  
        int n = a.length;  
        for (int i = 0; i < n; i++) {  
            for (int j = i + 1; j < n; j++) {  
                if (a[j] < a[i]) {  
                    int temp = a[i];  
                    a[i] = a[j];  
                    a[j] = temp;  
                }  
            }  
        }  
    }  
    
    public static void main(String[] args) {    
        int a[] = {35, 10, 31, 11, 26};    
        
        System.out.println("Before sorting array elements are - ");    
        print(a);  
        bubbleSort(a);  
        
        System.out.println();  
        System.out.println("After sorting array elements are - ");    
        print(a);      
    }    
}