In this chapter we shall learn about below topics:
1.1 Definition
1.2 Steps for performing Bubble Sort
1.3 Understanding Bubble Sort with an example
1.4 Implementation of Bubble Sort in C
1.5 Output of the program
1.6 Time complexity analysis of Bubble Sort
1.1 Definition:
Bubble sort is a sorting algorithm. It will sort by checking if the next element is greater the present element, if greater then it will swap the elements.
1.2 Steps for performing Bubble Sort:
1. In bubble sort we use 2 for loops. Outer loop and one inner loop.
2. For every element from the outer loop, we iterate through the inner element every time, and we compare the element from outer element to the element from the inner array element. If it is greater than we swap the elements.
3. At the end of the first iteration, the largest element will be at the end, similarly at the end of 2nd iteration 2nd highest element will be in n-1 position.
4. As we see that after every iteration highest element will be on the top, hence we call it as bubble sort.
1.3 Understanding Bubble Sort Using an example:
Consider the array:
[ 3, 4, 1, 2, 8, 5 ]First pass:
First we will check if 3 > 4, false, no swapping
[ 3, 4, 1, 2, 8, 5 ] -> [ 3, 4, 1, 2, 8, 5 ]
again we will check if 4 > 1, true, swap
[ 3, 4, 1, 2, 8, 5 ] -> [ 3, 1, 4, 2, 8, 5 ]
again we will check if 4 > 2, true, swap
[ 3, 1, 4, 2, 8, 5 ] -> [ 3, 1, 2, 4, 8, 5 ]
again we will check if 4 > 8, false, no swap
[ 3, 1, 2, 4, 8, 5 ] -> [ 3, 1, 2, 4, 8, 5 ]
again we will check if 8 > 5, true, swap
[ 3, 1, 2, 4, 8, 5 ] -> [ 3, 1, 2, 4, 5, 8 ]Hence after first pass, the largest element will be at the end. And we can ignore comparing the last element as it is the largest.
Second pass:
check if 3 > 1 True, swap
[ 3, 1, 2, 4, 5, 8 ] -> [1, 3, 2, 4, 5, 8 ]
check if 3 > 2 True, swap
[ 1, 3, 2, 4, 5, 8 ] -> [ 1, 2, 3, 4, 5, 8 ]
check if 3 > 4 false, don’t swap
[ 1, 2, 3, 4, 5, 8 ] -> [ 1, 2, 3, 4, 5, 8 ]
check if 4 > 5 false, don’t swap
[ 1, 2, 3, 4, 5, 8 ] -> [ 1, 2, 3, 4, 5, 8 ]
check if 5 > 8 false, don’t swap
[ 1, 2, 3, 4, 5, 8 ] -> [ 1, 2, 3, 4, 5, 8 ]
In the second pass, 2nd largest element will be at n-1 place.
Third pass:
In third pass the result will be the same as all the elements have been sorted.
In bubble sort, we use 2 loops. Outer loop is to loop n times and inner loop for swapping.
As you can see above, after 2nd pass all the elements are in the sorted order. Hence we can break the loop if no swapping done by the inner loop after third pass, hence saving the time.
1.4 Implementation of Bubble Sort in C
#include<stdio.h>
void print_array(int array[], int length)
{
int index = 0;
printf("The sorted array is \n");
for(index = 0 ; index < length ; index++)
{
printf("%d\n",array[index] );
}
}
void swap (int *num_1, int *num_2)
{
int temp = *num_1;
*num_1 = *num_2;
*num_2 = temp;
}
void bubble_sort (int array[], int length)
{
int outer_loop = 0;
int inner_loop = 0;
for(outer_loop = 0; outer_loop < length - 1; outer_loop ++)
{
for(inner_loop = 0; inner_loop < length - outer_loop - 1 ; inner_loop ++)
{
if(array [inner_loop] > array[inner_loop+1])
{
swap(&array[inner_loop], &array [inner_loop+1]);
}
}
}
}
int main()
{
int length = 0;
int array[100];
int index = 0;
printf("Enter the length of the array\n");
scanf("%d", &length);
printf("Enter the array elements of length %d\n", length);
for (index = 0; index < length; ++index)
{
scanf("%d", &array[index]);
}
bubble_sort(array, length);
print_array(array, length);
}1.5 Output:
Enter the length of the array
5
Enter the array elements of length 5
5
4
3
2
1
The sorted array is
1
2
3
4
51.6 Time Complexity analysis of Bubble sort:
From the above code, we can see that it always compares between 2 elements.
In the first pass, it will do n-1 comparisons
In the second pass, it will do n-2 comparisons
Similarly, we shall continue to compare elements, till it will become 1.
Hence the above sum can be written as:
(n-1) + (n-2) + (n-3) . . . + 1
It can be reduced to (n * (n -1))/2
-> 0.5 n^2 + 0.5 n
-> n^2
Hence the worst case will be O(n^2)