In this tutorial, we’re going to learn how the bubble sort algorithm works. Let’s get started:

Table of Contents

1. Explanation
2. Visualization
3. Implementation in Java
4. Implementation in C
5. Implementation in C++
6. Time Complexity

Explanation

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions according to order criteria. The order can be ascending or descending. Let’s assume, we need to sort an array in ascending order using Bubble sort. To do this, we need to follow these steps:

1. Compare the first and second items. If the first item is greater than the second item, they are swapped.
2. Then compare the second and the third items. Swap them if they are not in order.
3. The above process goes on until the array is being sorted.

Visualization

Let’s have a look at the visualization of Bubble sort algorithm:

Implementation in Java

Bubble sort in Java:

import java.util.Arrays;

class BubbleSort {
  void bubbleSort(int array[]) {
    int size = array.length;

    // run loops
    for (int i = 0; i < size - 1; i++)
      for (int j = 0; j < size - i - 1; j++)

        // change > to < for descending order
        if (array[j] > array[j + 1]) {

          // swap
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  // use bubble sort
  public static void main(String args[]) {
    int[] data = {9, 1, 4, 6, 3};
    BubbleSort bs = new BubbleSort();
    bs.bubbleSort(data);
    System.out.println("Sorted in ascending order:");
    System.out.println(Arrays.toString(data));
  }
}

Implementation in C

Bubble sort in C:

#include <stdio.h>

void bubbleSort(int array[], int size) {

  // run loops
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {

      // change > to < for descending order
      if (array[i] > array[i + 1]) {

        // swap
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// sort
int main() {
  int data[] = {9, 1, 4, 6, 3};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);

  printf("Sorted ascending order:\n");
  for (int i = 0; i < size; ++i) {
    printf("%d  ", data[i]);
  }
  printf("\n");
}

Implementation in C++

Bubble sort in C++:

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size) {

  // run loops
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {

      // change > to < for descending order
      if (array[i] > array[i + 1]) {

        // swap
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// sort
int main() {
  int data[] = {9, 1, 4, 6, 3};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);

  cout << "Sorted in ascending order:\n";
  for (int i = 0; i < size; ++i) {
    cout << "  " << data[i];
  }
  cout << "\n";
}

Time Complexity

There are two loops. So the complexity is n*n = n2. The time complexity (both average and worst) of Bubble Sort is O(n2).