Bubble sort is one of the simplest sorting techniques. It works as follows,
Assuming a list with n elements.
Compare the FIRST element with the SECOND element. If the first element is greater than the second element then swap them.
Now, Compare the SECOND element with the THIRD element.If the second element is greater than the third element then swap them.
Continue the same procedure till the last element in the list. By doing in this way at the end of one iteration through the list, the biggest element will be moved to the last position.
Now in the second iteration repeat the same process with first n-1 elements. This ensure the second biggest element in the (n-1)
th position.
later in the third iteration repeat the same process with first n-2 elements. This ensures the third biggest element in the (n-2)th position.
like this after n iterations the list gets sorted.
One can imagine this like, in each iteration the biggest element gets bubbled up the list to occupy its correct position in the list.
Example:
Consider the list
3 2 5 1 4
Iteration 1 :
compare 3 with 2, as 3>2 swap them. result 2 3 5 1 4
compare 3 with 5, as 3<5 do not swap
compare 5 with 1, as 5>1 swap them. result 2 3 1 5 4
compare 5 with 4, as 5>4 swap them. result 2 3 1 4 5
End of iteration 1. Now observe that the biggest element is placed in the n th position.
Now for second iteration consider only n-1 elements. no need to worry about the n th postion as it is already placed in its exact position.
Iteration 2 :
2 3 1 4 5
compare 2 with 3, as 2<3 do not swap
compare 3 with 1, as 3>1 swap them. result 2 1 3 4 5
compare 3 with 4, as 3<4 do not swap
End of Iteration 2.
Now consider n-2 elements.
2 1 3 4 5 and continue the same process.
Below is an example c code that takes 5 elements as input and outputs a sorted list (using bubble sort approach).
#include<stdio.h>
void main()
{
int i,a[5],j,temp,k;
clrscr();
printf("\nEnter 5 numbers to sort ::\n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
printf("\nElements before sort : ");
for(i=0;i<5;i++)
printf("%d\t",a[i]);
printf("\n====Bubble sort====\n");
for(i=0;i<5;i++)
{
for(j=0;j<5-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
printf("\nElements after round %d : ",i+1 );
for(k=0;k<5;k++)
printf("%d\t",a[k]);
}
printf("\n\nFinal List: ");
for(i=0;i<5;i++)
printf("%d\t",a[i]);
getch();
}
In the above example observe the code highlighted. This gives the core logic.
There are two loops that run n times. Therefore the worst case running time will be O(n2).
- Minimum number of swaps 0 ( if the list is already sorted)
- Maximum swaps n(n-1)/2 ( if the list is in descending order)
- Minimum comparisions n(n-1)/2
- Maximum comparisions n(n-1)/2
For comparison of various sorting algorithms
click here
