Bubble Sort

Sorting Algorithm

Share

In this tutorial, we will learn about Bubble Sort which is one of the easiest sorting algorithms.

How Bubble Sort works?

We use Bubble Sort algorithm to sort the elements in either ascending or descending order.

We compare two adjacent elements and swap them only if they are not in the correct position.

Points to remember

  • Bubble Sort requires (n – 1) pass to sort an array arr having n elements.
  • In each pass, two adjacent elements arr[i] and arr[i + 1] are compared and if they are not in order then they are swapped.
  • In an given pass, we have total (n – k) comparisons, where n is the number of elements and k is the pass number.

So, if an unsorted array has n elements then we will need total (n - 1) pass to sort the elements in either ascending or descending order.

And in any given pass k, we will make (n - k) comparison.

Pseudo code of Bubble Sort algorithm

/**
 * a[0:n-1] is an array of n elements.
 * temp is a variable to facilitate exchange.
 */
BubbleSort(a, n)
Begin
  for k = 1 to n-1 increment by 1 do  // where, k is for the pass
    for j = 0 to n – k – 1 increment by 1 do  // this is for comparison
      if a[j] > a[j+1] then  
        Set temp = a[j];
        Set a[j] = a[j+1];
        Set a[j+1] = temp;
      endif
    endfor
  endfor
End

Sorting elements using Bubble Sort algorithm

Let's say we have the following unsorted numbers 5, 4, 3, 1, 2 and we want to sort them in ascending order.

So, there are total 5 elements. Hence we will need (5 - 1) i.e. 4 pass.

Pass #1

In Pass #1 we will perform (n - k) i.e. (5 - 1) i.e. 4 comparisons.

Start: 5, 4, 3, 1, 2

Compare 5 and 4: swap as they are not in order
[5, 4], 3, 1, 2 ---> 4, 5, 3, 1, 2

Compare 5 and 3: swap as they are not in order
4, [5, 3], 1, 2 ---> 4, 3, 5, 1, 2

Compare 5 and 1: swap as they are not in order
4, 3, [5, 1], 2 ---> 4, 3, 1, 5, 2

Compare 5 and 2: swap as they are not in order
4, 3, 1, [5, 2] ---> 4, 3, 1, 2, 5

End: 4, 3, 1, 2, 5

Pass #2

In Pass #2 we will perform (5 - 2) i.e. 3 comparisons.

Start: 4, 3, 1, 2, 5

Compare 4 and 3: swap as they are not in order
[4, 3], 1, 2, 5 ---> 3, 4, 1, 2, 5

Compare 4 and 1: swap as they are not in order
3, [4, 1], 2, 5 ---> 3, 1, 4, 2, 5

Compare 4 and 2: swap as they are not in order
3, 1, [4, 2], 5 ---> 3, 1, 2, 4, 5

End: 3, 1, 2, 4, 5

Pass #3

In Pass #3 we will perform (5 - 3) i.e. 2 comparisons.

Start: 3, 1, 2, 4, 5

Compare 3 and 1: swap as they are not in order
[3, 1], 2, 4, 5 ---> 1, 3, 2, 4, 5

Compare 3 and 2: swap as they are not in order
1, [3, 2], 4, 5 ---> 1, 2, 3, 4, 5

End: 1, 2, 3, 4, 5

Pass #4

In Pass #4 we will perform (5 - 4) i.e. 1 comparison.

Start: 1, 2, 3, 4, 5

Compare 1 and 2: they are in order so, no swapping required
1, 2, 3, 4, 5 ---> 1, 2, 3, 4, 5

End: 1, 2, 3, 4, 5

And we have the elements sorted in ascending order using Bubble Sort algorithm.

Code

In the following section we have Bubble Sort in Java, C, PHP, Python and JavaScript.

#include <stdio.h>

//function declaration
void bubbleSort(int *a, int n);

int main(){
  //variable declaration
  int arr[5], i;
  
  //input
  for(i = 0; i < 5; i++)
    scanf("%d", &arr[i]);
  
  //sort
  bubbleSort(arr,5);  //sending arr address and no. of elements
  
  //output
  for(i = 0; i < 5; i++)
    printf("%d\n", arr[i]);
    
  return 0;
}

//function definition
void bubbleSort(int *a, int n){
  int k, j, temp;
  for(k = 1; k <= n-1; k++){
    for(j = 0; j <= n-k-1; j++){
      if(a[j] > a[j+1]){
        temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
      }
    }
  }
}
public class BubbleSort {
  public static void main(String args[]) {

    // unsorted array
    int arr[] = {5, 4, 3, 1, 2};

    // total elements in the array
    int len = arr.length;

    int k, j, temp;

    // sorting
    for(k = 1; k <= len - 1; k++) {
      for(j = 0; j <= len - k - 1; j++) {
        if(arr[j] > arr[j + 1]) {
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }

    // result
    for(k = 0; k < len; k++) {
      System.out.print(arr[k] + " ");
    }

  }
}
<?php

// unsorted array
$arr = [5, 4, 3, 1, 2];

// number of elements in the array
$len = count($arr);

// sorting
for($k = 1; $k <= $len - 1; $k++) {
  for($j = 0; $j <= $len - $k - 1; $j++) {
    if($arr[$j] > $arr[$j + 1]) {
      $temp = $arr[$j];
      $arr[$j] = $arr[$j + 1];
      $arr[$j + 1] = $temp;
    }
  }
}

// print sorted elements
foreach($arr as $k) {
  print($k . " ");
}
// unsorted array
arr = [5, 4, 3, 1, 2]

// number of elements in the array
length = len(arr)

// sorting
for k in range(1, length):
  for j in range(0, length - k):
    if arr[j] > arr[j + 1]:
      temp = arr[j]
      arr[j] = arr[j + 1]
      arr[j + 1] = temp

// print sorted elements
for item in arr:
  print(item)
// unsorted array
var arr = [5, 4, 3, 1, 2];

// number of elements in the array
var len = arr.length;

// sorting
for(var k = 1; k <= len - 1; k++) {
  for(var j = 0; j <= len - k - 1; j++) {
    if(arr[j] > arr[j + 1]) {
      var temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
}

// print sorted elements
for(var i = 0; i < len; i++) {
  console.log(arr[i]);
}

Time Complexity

Worst-case and average time complexity of Bubble sort is O(n2), where n is the number of items being sorted.

When n is very large then Bubble sort is not a suitable choice to sort the elements.

Check out Quick Sort.

Share