Bubble Sort Algorithm

Bubble sort is the simplest sorting algorithm. It works by iterating the input array from the first element to last. We compare each pairs of elements and swapping them if they are in wrong order. The algorithm got its name from the way larger element “bubble” to the end of the array.

Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Third Pass
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Fourth Pass
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Implementation of Bubble Sort

Below is the C implementation of bubble sort algorithm.

#include<stdio.h>
void printArray(int arr[], int size){
    for(int i = 0; i < size; i++){
      printf("%d ", arr[i]);
    }
    printf("\n");
}

void swap(int *xp, int *yp){
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void bubbleSort(int arr[], int size){
  for(int pass = 0; pass < size-1; pass++){
    for(int i = 0; i < size-pass-1; i++){ if(arr[i] > arr[i+1]){
        swap(&arr[i],&arr[i+1]);
      }
    }
  }
}

// Driver Program
int main(){
  int arr[] = {5,3,1,9,8,2,4,7};
  int size = sizeof(arr)/sizeof(arr[0]);
  bubbleSort(arr, size);
  printf("======Sorted Array is======\n");
  printArray(arr, size);
  return 0;
}

Illustration of above program

Analysis of the Bubble Sort Algorithm

In each pass of bubble sort one element move to last position. so recurrence relation of bubble sort can be written as:

$$T(n) = T(n-1) + n$$

Solving this recurrence relation we get time complexity of \(\mathcal O(n^2)\).

Optimization in Bubble Sort Algorithm

Bubble sort take \((n-1)\) pass and in each pass it scan the whole array. It may happen that array is sorted before  \((n-1)\) pass but algorithm didn’t terminate as in the above illustration. We can optimize bubble sort by terminating the algorithm in that pass in which there is no swap occurs. Below is the optimize implementation of bubble sort:

#include<stdio.h>
#include<stdbool.h>
void printArray(int arr[], int size){
    for(int i = 0; i < size; i++){
      printf("%d ", arr[i]);
    }
    printf("\n");
}

void swap(int *xp, int *yp){
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void bubbleSort(int arr[], int size){
  bool swapped;
  for(int pass = 0; pass < size-1; pass++){
    swapped = false;
    for(int i = 0; i < size-pass-1; i++){ if(arr[i] > arr[i+1]){
        swap(&arr[i],&arr[i+1]);
        swapped = true;
      }
    }
    if(swapped == false)
      break;
  }
}

// Driver Program
int main(){
  int arr[] = {5,3,1,9,8,2,4,7};
  int size = sizeof(arr)/sizeof(arr[0]);
  bubbleSort(arr, size);
  printf("======Sorted Array is======\n");
  printArray(arr, size);
  return 0;
}

Analysis of the above implementation

Worst and Average Case Time Complexity: \(\mathcal O(n^2) \). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: \(\mathcal O(n) \). Best case occurs when array is already sorted.

Auxiliary Space: \(\mathcal O(1)\)

Boundary Cases: Bubble sort takes minimum time (\(\mathcal O(n) \)) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm. In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (\(2n\)). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their \(x\) coordinate at a specific scan line (a line parallel to \(x\) axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines (Source: Wikipedia)

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.