Bubble Sort

Sorting Algorithm

Share

In this tutorial we will learn to sort elements using Bubble Sort algorithm.

About Bubble Sort

In this technique we sort the given elements in ascending or descending order by comparing two adjacent elements at a time and placing them in correct position.

  • Bubble sort requires n – 1 pass to sort an array a having n elements.
  • In each pass every adjacent elements a[i] and a[i+1] is compared and if they are not in order then they are swapped.
  • In each pass we have n – k comparisons, where n is the number of elements and k is the pass number.
    So, 1st pass requires n – 1 comparisons,
    kth pass requires n – k comparisons and
    the last pass requires 1 comparison.

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 by 1 do  //this is for pass
        for j = 0 to n – k – 1 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

Code

In the following code section we have Bubble Sort algorithm in C and Java programming language.

#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] + " ");
    }

  }
}

Time Complexity

Worst-case and average 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.

Share