Bubble Sort

Bubble sort is very simple sorting technique, in this each element compare with every other element in the list. This is also called sinking sort. It continuously compares the element with the adjacent item and swap if the element are in wrong order. If the element at lower index is greater than the element at the higher index, then the two elements are interchanged as the element is placed before the bigger one.

This process is continue working till the largest element move to the highest index position.

Bubble sort example

Let us an array has the following element.

A[] = {10, 43, 23, 56, 16}

These are the bubble sorting technique.

Pass 1

Compare A[0] and A[1], since A[0] < A[1] then no interchange.

Compare A[1] and A[2], since A[1] > A[2] then interchange.

Compare A[2] and A[3], since A[2] < A[3] then no interchange.

Compare A[3] and A[4], since A[3] > A[4] then interchange.

Pass 2

Compare A[0] and A[1], since A[0] < A[1] then no interchange.

Compare A[1] and A[2], since A[1] < A[2] then no interchange.

Compare A[2] and A[3], since A[2] > A[3] then interchange.

Compare A[3] and A[4], since A[3] < A[4] then no interchange.

Bubble Sorting Algorithm

STEP 1: Repeat Step 2 For 1=0 to N-1
STEP 2: Repeat for J = 0 to N - I
STEP 3: IF A[J] > A[J+1]
		SWAP A[J] and A[J+1]
	[END of INNER LOOP]
[END of OUTER LOOP]
STEP 4: EXIT

Complexity of Bubble sort

Suppose n is the number of element in an array.

f(n) = (n-1)+(n-2)+(n-3)+.....+3+2+1
f(n) = n(n-1)/2
f(n) = n2/2 + O(n) 
     = O(n2)

Bubble Sort Program in C

#include<stdio.h>

int main(){

	int count, temp, i, j, array[100];

	printf("Enter the number of elements : ");
	scanf("%d",&count);

	printf("Enter %d numbers : ",count);

	for(i=0;i<count;i++)
	scanf("%d",&array[i]);

	for(i=count-2;i>=0;i--){
	  for(j=0;j<=i;j++){
		if(array[j]>array[j+1]){
		   temp=array[j];
		   array[j]=array[j+1];
		   array[j+1]=temp;
		}
	  }
	}

	printf("Sorted list : ");
	for(i=0;i<count;i++)
		printf(" %d",array[i]);

	return 0;
}

Output of the above program

Enter the number of elements : 5
Enter 5 numbers : 34
21
67
54
89
Sorted list :  21 34 54 67 89