How does Bubble sort works?

Bubble sort is a comparison based sorting algorithm. It works like following.

We perform series of iterations to ‘bubble up’ the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up to the last spot. In the second iteration element ‘4’ will be moved to the last but first spot and so on. The following sequence shows one iteration. In each step in the iteration, successive pairs of elements are compared, if they violate the order, swap it.

3<->1 4 5 2
1 3<->4 5 2
1 3 4<->5 2
1 3 4 5<->2
1 3 4 2 5

This iteration is repeated until the entire array is sorted. In the first iteration, there will be n-1 comparisons. In the second iteration there will be n-2 comparisons. The number of comparisons decreases with each iteration. The last iteration will have only one comparison. The following code shows the implementation of the above approach. The time complexity of bubble sort is O(n^2).

#include <iostream>
using namespace std;

//helper method to swap two elements
void swap( int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}
//bubble sort function, takes array and it's size
//as parameters
void bubble_sort(int *array, int n)
{
 int i,j;
 //outer loop runs for n-1 iterations
 for( i = 0 ; i < n-1 ; i++)
 {
  //inner loop is for comparisons
  //in each iteration comparisons reduce by 1
  for( j = 0 ; j < n-1-i ; j++)
  {
   //if elements are out-of-order, swap them
   if( array[j] > array[j+1] )
    swap(array[j], array[j+1]);
  }
 }
}
int main()
{
 int n;
 cin>>n;
 int *array = new int[n];
 int i;
 for( i = 0 ; i < n ; i++ )
 {
  cin>>array[i];
 }
 bubble_sort(array,n);
 for( i = 0 ; i < n ; i++)
 {
  cout<<array[i]<<" ";
 }
 return 0;
}

In bubble sort there is a mechanism to detect if the input array is already sorted. In any iteration, if there are no swappings performed, then we can conclude that the array is sorted. Here is how we can modify the bubble sort to implement this.

void bubble_sort(int *array, int n)
{
 int i,j;
 bool swap_flag = false;
 //outer loop runs for n-1 iterations
 for( i = 0 ; i < n-1 ; i++)
 {
  //inner loop is for comparisions
  //in each iteration the comparisions count reduce by 1
  for( j = 0 ; j < n-1-i ; j++)
  {
   //if elements are out-of-order, swap them
   if( array[j] > array[j+1] )
   {
    swap(array[j], array[j+1]);
    swap_flag = true;
   }   
  }
  //if no swaps are performed in the inner loop, break
  if( !swap_flag )
   break;
 }
}

Leave a Reply Cancel reply