The algorithm works on the principle (For ascending order)

• Linearly traverse an array
• Start from the leftmost item
• If left item is greater than its right item swap them

That is arr[i] > arr[i+1] swap them

Let’s take an example, we have a list of number stored in array

1. ( 28 6 4 2 24 ) -> ( 6 28 4 2 24 ) : Swapped 28 & 6 since 28 > 6
2. ( 6 28 4 2 24 ) -> ( 6 4 28 2 24 ) : Swapped 28 & 4 since 28 > 4
3. ( 6 4 28 2 24 ) -> ( 6 4 2 28 24 ) : Swapped 28 & 2 since 28 > 2
4. ( 6 4 2 28 24 ) -> ( 6 4 2 24 28 ) : Swapped 28 & 24 since 28 > 24

As you can see in pass 1 we got the largest element at the end of the array so that part is already sorted. Which is why its called bubble sort

• Like in a soda drink the largest bubble traverse to the stop first
• Here the largest item traversed to right first

If there is any pass where no swap happens, do not implement any further passes since the array is already sorted.

  
#include<stdio.h>

void swap(int *var1, int *var2) 
{ 
    int temp = *var1; 
    *var1 = *var2; 
    *var2 = temp; 
} 

// Here we are implementing bubbleSort
void bubbleSort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i < n-1; i++){
        // initializing swapped to 0 (no swaps happenned yet)
        int swapped = 0;

       // Since, after each iteration righmost i elements are sorted   
        for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) 
            {
                swap(&arr[j], &arr[j+1]);
                // change swap value as swap has happenned
                swapped = 1;
            }
        }
        // if no swaps happen stop don't impliment further passes/iterations
        if(!swapped)
            break;
    }
} 

/* Function to print array */
void display(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
} 

// Main function to run the program
int main() 
{ 
    int array[] = {10, 20, 30, 40, 50}; 
    int size = sizeof(array)/sizeof(array[0]); 

    printf("Before bubble sort: \n");
    display(array, size); 

    bubbleSort(array, size);

    printf("After bubble sort: \n"); 
    display(array, size); 
    return 0; 
}
  

  
#include<iostream>
using namespace std;

void swap(int *var1, int *var2)
{
    int temp = *var1;
    *var1 = *var2;
    *var2 = temp;
}

// Here we will implement bubbleSort.
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)
   {
        // for optimization when array is already sorted & no swapping happens
       bool swapped = false;
       
       //Since, after each iteration rightmost i elements are sorted.
       for (j = 0; j < n-i-1; j++) 
       { 
           if (arr[j] > arr[j+1]){
                swap(&arr[j], &arr[j+1]);
                // swapping happenned so change to true
                swapped = true;
           }
       }
       // if no swaps happenned in any of the iteration
       // array has become sorted so stop with the passes
       if(swapped == false)
            break;
   }
}

// Function to print array.
void display(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout<< arr[i]<< " ";
    cout<< endl;
}

//Main function to run the program.
int main()
{
    int array[] = {10, 20, 30, 40, 50};
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<<"Before bubble sort: \n";
    display(array, size);//Calling display function to print unsorted array.
    
    bubbleSort(array, size);
    
    cout<<"After bubble sort: \n";
    display(array, size);//Calling display function to print sorted array.
    
    return 0;
}
  

  
// Time Complexity : O(N^2)
// Space Complexity : O(1)
class Main
{
    static void bubbleSort(int a[])
    {
        int len = a.length; // calculating the length of array
        for (int i = 0; i < len-1; i++) {

            // for optimization when array is already sorted & no swapping happens
            boolean swapped = false;
            for (int j = 0; j < len - i - 1; j++) 
            { 
                if (a[j] > a[j + 1]) //comparing the pair of elements
                {
                    // swapping a[j+1] and a[i]
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    // swapping happened so change to true
                    swapped = true;
                }
            }

            // if no swaps happened in any of the iteration
            // array has become sorted so stop with the passes
            if(swapped == false)
                break;

        }
    }

    /* Prints the array */
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; i++)
            System.out.print(a[i] + " "); //printing the sorted array

        System.out.println();
    }

    // Main method to test above
    public static void main(String args[])
    {
        int arr[] = {10, 20, 30, 40, 50};


        System.out.print("Before bubble sort:\n");
        printArray(arr);

        bubbleSort(arr);//calling the bubbleSort function

        System.out.println("After bubble sort:");
        printArray(arr); //calling the printArray function
    }
}
	

	
Before bubble sort: 
10 20 30 40 50 
After bubble sort: 
10 20 30 40 50 
	

• Easy to implement
• Cool to implement
• Gives the largest value of the array in the first iteration itself.
• Or the smallest value of array in the first iteration itself (Minor tweak in implementation)
• No demand for large amounts of memory for operation

• Noob (Bad) algorithm 😀
• Very horrible time complexity of O(n²)

1. Average and worst-case time complexity: o(n²)
2. Best case time complexity: n when the array is already sorted.
3. Worst case: when the array is reverse sorted.

Number of comparisons in Bubble sort is reduces by 1 in each pass.

Example – For array size 5,

1. In Pass 1: 4 comparisons
2. In Pass 2: 3 comparisons
3. In Pass 3: 2 comparisons
4. In Pass 4: 1 comparison

Thus, for n sized array the total number of comparisons, therefore, is (n – 1) + (n – 2)…(2) + (1) = n(n – 1)/2