Join our newsletter for the latest updates.

Bubble Sort Algorithm

In this tutorial, you will learn the working of bubble sort algorithm. Also, you will find the implementation of bubble sort in Python, Java, C, and C++.

The bubble sort algorithm compares two adjacent elements and swaps them if they are not in the intended order. For example,

Suppose we have an unsorted array with elements: 45, 1, 4.

Here, the bubble sort algorithm compares the first element 45 and second element 1. Since 45 is greater than 1, they are swapped (1, 45, 4).

Similarly, the new second element is compared with the next element. This process continues until all the elements are sorted.


Working of Bubble Sort Algorithm

Here, we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

  1. Starting from the first index, compare the first and the second elements.
  2. If the first element is greater than the second element, they are swapped.
  3. Now, compare the second and the third elements. Swap them if they are not in order.
  4. The above process goes on until the last element.
    Compare two adjacent elements and swap them if the first element is greater than the next element
    Compare the Adjacent Elements

2. Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

Continue the swapping and put the largest element among the unsorted list at the end
Put the largest element at the end

In each iteration, the comparison takes place up to the last unsorted element.

Swapping occurs only if the first element is greater than the next element
Compare the adjacent elements

The array is sorted when all the unsorted elements are placed at their correct positions.

The array is sorted if all the elements are kept in the right order.
The array is Sorted if all elements are kept in the right order

Bubble Sort Algorithm

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Implementation of Bubble Sort in Python, Java and C/C++

# Bubble sort in Python

def bubbleSort(array):
    
  # loop through each element of array
  for i in range(len(array)):

    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping occurs if 
        # the first element is greater than second
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [-2, 45, 0, 11, -9]

# call the bubbleSort() method
bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java

import java.util.Arrays;

class Main {

  // method to perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
    
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)

        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if 
          // the first element is greater than second
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  // main method
  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call the method using the class name Main
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}
// Bubble sort in C

#include <stdio.h>

// function to perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if 
        // the first element is greater than second
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

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

// main function
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  
  // call function to print the array
  printArray(data, size);
}
// Bubble sort in C++

#include <iostream>
using namespace std;

// function to perform bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < (size-1); ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - (step-1); ++i) {

      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping occurs if
        // the first element is greater than second
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// function to print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

// main function
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";
  
  // call the function to print the array
  printArray(data, size);
}

Optimized Bubble Sort Algorithm

In the above algorithm, all the comparisons are made even if the array is already sorted.

This increases the execution time.

To solve this, we can introduce an extra variable swapped. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is set false.

After an iteration, if there is no swapping, the value of swapped will be false. This means elements are already sorted and there is no need to perform further iterations.

This will reduce the execution time and helps to optimize the bubble sort.

Algorithm for optimized bubble sort is

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

Implementation of Optimized Bubble Sort

# Optimized bubble sort in python

def bubbleSort(array):
    
  # loop through each element of array
  for i in range(len(array)):
        
    # keep track of swapping
    swapped = False
    
    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping occurs if
        # the first element is greater than second
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp

        swapped = True
          
    # no swapping means the array is already sorted
    # so no need of further comparison
    if not swapped:
      break

data = [-2, 45, 0, 11, -9]

# call the bubbleSort() method
bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)
// Bubble sort in Java

import java.util.Arrays;

class Main {

  // method to perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < (size-1); i++) {
    
      // check if swapping occurs
      boolean swapped = false;
      
      // loop to compare adjacent elements
      for (int j = 0; j < (size-i-1); j++) {

        // compare two array elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if 
          // the first element is greater than second
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
          
          swapped = true;
        }
      }
      // no swapping means the array is already sorted
      // so no need of further comparison
      if (!swapped)
        break;

    }
  }

  // main method
  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call the method using the class name Main
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}
// Bubble sort in C

#include <stdio.h>

// method to perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
    
    // check if swapping occurs  
    int swapped = 0;
    
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if 
        // the first element is greater than second
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }
    
    // no swapping means the array is already sorted
    // so no need of further comparison
    if (swapped == 0) {
      break;
    }
    
  }
}

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

// main method
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  
  // call function to print the array
  printArray(data, size);
}
// Optimized bubble sort in C++

#include <iostream>
using namespace std;

// function to perform bubble sort
void bubbleSort(int array[], int size) {
    
  // loop to access each array element
  for (int step = 0; step < (size-1); ++step) {
      
    // check if swapping occurs
    int swapped = 0;
    
    // loop to compare two elements
    for (int i = 0; i < (size-step-1); ++i) {
        
      // compare two array elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping occurs if 
        // the first element is greater than the second 
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }

    // no swapping means the array is already sorted
    // so no need of further comparison
    if (swapped == 0)
      break;
  }
}

// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

// main function
int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";
  
  // call the function to print the array
  printArray(data, size);
}

Complexity of Bubble Sort

Bubble Sort is one of the simplest sorting algorithms that compare adjacent elements.

Cycle Number of Comparisons
1st (n-1)
2nd (n-2)
3rd (n-3)
....... ......
last 1

Here, number of comparisons

(n - 1) + (n - 2) + (n - 3) +.....+ 1 = n(n - 1) / 2

nearly equals to n2

Hence, Complexity: O(n2)

Also, if we simply observe the number of loops. The algorithm implements two loops. Hence, the complexity is n*n = n2

1. Time Complexities

  • Worst Case Complexity:O(n2)
    If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
  • Best Case Complexity:O(n)
    If the array is already sorted, then there is no need for sorting.
  • Average Case Complexity:O(n2)
    It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

  • Space complexity is O(1) because an extra variable temp is used for swapping.
  • In the optimized bubble sort algorithm, another variable swapped is used. Hence, the space complexity will be O(2).

Applications of Bubble Sort

Bubble sort is used in the following cases where

  • the complexity of the code does not matter.
  • a short and simple code is preferred.

Other Sorting Algorithms