Bubble sort is a very simple method that sorts the array elements by repeatedly moving the
largest element to the highest index position of the array segment (in case of arranging elements in ascending order). In bubble sorting, consecutive adjacent pairs of elements in the array are compared with each other. If the element at the lower index is greater than the element at the higher index, the two elements are interchanged so that the element is placed before the bigger one. This process will continue till the list of unsorted elements exhausts.
This procedure of sorting is called bubble sorting because elements ‘bubble’ to the top of the
list. Note that at the end of the first pass, the largest element in the list will be placed at its proper position.
The basic methodology of the working of bubble sort is given as follows :-
(a) In Pass 1, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–2] is compared with A[N–1]. Pass 1 involves n–1 comparisons
and places the biggest element at the highest index of the array.
(b) In Pass 2, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–3] is compared with A[N–2]. Pass 2 involves n–2 comparisons
and places the second biggest element at the second highest index of the array.
(c) In Pass 3, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared with A[3], and so on. Finally, A[N–4] is compared with A[N–3]. Pass 3 involves n–3 comparisons
and places the third biggest element at the third highest index of the array.
(d) In Pass n–1, A[0] and A[1] are compared so that A[0]<A[1]. After this step, all the elements of the array are arranged in ascending order.
To discuss bubble sort in detail, let us consider an array A[] that has the following elements:
A[] = {30, 52, 29, 87, 63, 27, 19, 54}
Pass 1 :-
(a) Compare 30 and 52. Since 30 < 52, no swapping is done.
(b) Compare 52 and 29. Since 52 > 29, swapping is done.
30, 29, 52, 87, 63, 27, 19, 54
(c) Compare 52 and 87. Since 52 < 87, no swapping is done.(d) Compare 87 and 63. Since 87 > 63, swapping is done.
30, 29, 52, 63, 87, 27, 19, 54
(e) Compare 87 and 27. Since 87 > 27, swapping is done.30, 29, 52, 63, 27, 87, 19, 54
(f) Compare 87 and 19. Since 87 > 19, swapping is done.30, 29, 52, 63, 27, 19, 87, 54
(g) Compare 87 and 54. Since 87 > 54, swapping is done.30, 29, 52, 63, 27, 19, 54, 87
Observe that after the end of the first pass, the largest element is placed at the highest index ofthe array. All the other elements are still unsorted.
Pass 2 :-
(a) Compare 30 and 29. Since 30 > 29, swapping is done.
29, 30, 52, 63, 27, 19, 54, 87
(b) Compare 30 and 52. Since 30 < 52, no swapping is done.(c) Compare 52 and 63. Since 52 < 63, no swapping is done.
(d) Compare 63 and 27. Since 63 > 27, swapping is done.
29, 30, 52, 27, 63, 19, 54, 87
(e) Compare 63 and 19. Since 63 > 19, swapping is done.29, 30, 52, 27, 19, 63, 54, 87
(f) Compare 63 and 54. Since 63 > 54, swapping is done.29, 30, 52, 27, 19, 54, 63, 87
Observe that after the end of the second pass, the second largest element is placed at the second highest index of the array. All the other elements are still unsorted.
Pass 3 :-
(a) Compare 29 and 30. Since 29 < 30, no swapping is done.
(b) Compare 30 and 52. Since 30 < 52, no swapping is done.
(c) Compare 52 and 27. Since 52 > 27, swapping is done.
29, 30, 27, 52, 19, 54, 63, 87
(d) Compare 52 and 19. Since 52 > 19, swapping is done. 29, 30, 27, 19, 52, 54, 63, 87
(e) Compare 52 and 54. Since 52 < 54, no swapping is done.Observe that after the end of the third pass, the third largest element is placed at the third highest index of the array. All the other elements are still unsorted.
Pass 4 :-
(a) Compare 29 and 30. Since 29 < 30, no swapping is done.
(b) Compare 30 and 27. Since 30 > 27, swapping is done.
29, 27, 30, 19, 52, 54, 63, 87
(c) Compare 30 and 19. Since 30 > 19, swapping is done.29, 27, 19, 30, 52, 54, 63, 87
(d) Compare 30 and 52. Since 30 < 52, no swapping is done.Observe that after the end of the fourth pass, the fourth largest element is placed at the fourth
highest index of the array. All the other elements are still unsorted.
Pass 5 :-
(a) Compare 29 and 27. Since 29 > 27, swapping is done.
27, 29, 19, 30, 52, 54, 63, 87
(b) Compare 29 and 19. Since 29 > 19, swapping is done.27, 19, 29, 30, 52, 54, 63, 87
(c) Compare 29 and 30. Since 29 < 30, no swapping is done.Observe that after the end of the fifth pass, the fifth largest element is placed at the fifth highest index of the array. All the other elements are still unsorted.
Pass 6 :-
(a) Compare 27 and 19. Since 27 > 19, swapping is done.
19, 27, 29, 30, 52, 54, 63, 87
(b) Compare 27 and 29. Since 27 < 29, no swapping is done.Observe that after the end of the sixth pass, the sixth largest element is placed at the sixth largest index of the array. All the other elements are still unsorted.
Pass 7 :-
(a) Compare 19 and 27. Since 19 < 27, no swapping is done.
** Algorithm for bubble sort **
BUBBLE_SORT(A, N)
Step 1: Repeat Step 2 For1= 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
The complexity of any sorting algorithm depends upon the number of comparisons. In bubble
sort, we have seen that there are N–1 passes in total. In the first pass, N–1 comparisons are made to place the highest element in its correct position. Then, in Pass 2, there are N–2 comparisons and the second highest element is placed in its position. Therefore, to compute the complexity of bubble sort, we need to calculate the total number of comparisons. It can be given as:
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)
Therefore, the complexity of bubble sort algorithm is O(n2). It means the time required to execute bubble sort is proportional to n2, where n is the total number of elements in the array
*******************
Programming Example
*******************
1. Write a program to enter n numbers in an array. Redisplay the array with elements being
sorted in ascending order.
#include<stdio.h>
#include<conio.h>
void read(int a[],int n);
void print(int a[],int n);
void bubblesort(int a[],int n);
void main()
{
int a[100],n;
clrscr();
printf("\n\t Enter of Element::::>");
scanf("%d",&n);
read(a,n);
print(a,n);
bubblesort(a,n);
getch();
}
void read(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("\n\t Enter of Array Elementa[%d]::::>",i);
scanf("%d",&a[i]);
}
}
void print(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("\n\t print of Array::::>%d",a[i]);
}
}
void bubblesort(int a[],int n)
{
int i,j,tmp;
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}
printf("\n\n\t after shorting:::");
print(a,n);
}
All c programming & algorithm 