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 Searching and Sorting 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 until the list of unsorted elements exhausts
This procedure of sorting is called bubble sorting because elements ‘bubble’ to the top of the list.
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}
Now, we will see sorting procedure, that will be implemented in each bubble sort pass, one by one.
Pass 1:
- Compare 30 and 52. Since 30 < 52, no swapping is done.
- Compare 52 and 29. Since 52 > 29, swapping is done.
30, 29, 52, 87, 63, 27, 19, 54 - Compare 52 and 87. Since 52 < 87, no swapping is done.
- Compare 87 and 63. Since 87 > 63, swapping is done.
30, 29, 52, 63, 87, 27, 19, 54 - Compare 87 and 27. Since 87 > 27, swapping is done.
30, 29, 52, 63, 27, 87, 19, 54 - Compare 87 and 19. Since 87 > 19, swapping is done.
30, 29, 52, 63, 27, 19, 87, 54 - 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 of the array. All the other elements are still unsorted.
Pass 2:
- Compare 30 and 29. Since 30 > 29, swapping is done.
29, 30, 52, 63, 27, 19, 54, 87 - Compare 30 and 52. Since 30 < 52, no swapping is done.
- Compare 52 and 63. Since 52 < 63, no swapping is done.
- Compare 63 and 27. Since 63 > 27, swapping is done.
29, 30, 52, 27, 63, 19, 54, 87 - Compare 63 and 19. Since 63 > 19, swapping is done.
29, 30, 52, 27, 19, 63, 54, 87 - 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:
- Compare 29 and 30. Since 29 < 30, no swapping is done.
- Compare 30 and 52. Since 30 < 52, no swapping is done.
- Compare 52 and 27. Since 52 > 27, swapping is done.
29, 30, 27, 52, 19, 54, 63, 87 - Compare 52 and 19. Since 52 > 19, swapping is done.
29, 30, 27, 19, 52, 54, 63, 87 - 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:
- Compare 29 and 30. Since 29 < 30, no swapping is done.
- Compare 30 and 27. Since 30 > 27, swapping is done.
29, 27, 30, 19, 52, 54, 63, 87 - Compare 30 and 19. Since 30 > 19, swapping is done.
29, 27, 19, 30, 52, 54, 63, 87 - 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:
- Compare 29 and 27. Since 29 > 27, swapping is done.
27, 29, 19, 30, 52, 54, 63, 87 - Compare 29 and 19. Since 29 > 19, swapping is done.
27, 19, 29, 30, 52, 54, 63, 87 - 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:
- Compare 27 and 19. Since 27 > 19, swapping is done.
19, 27, 29, 30, 52, 54, 63, 87 - 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:
- Compare 19 and 27. Since 19 < 27, no swapping is done.
Bubble Sort Algorithm
BUBBLE_SORT(A, N)
Step 1: Repeat Step 2 For1= to N-1
Step 2: Repeat ForJ= toN-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: EXITIn this algorithm, the outer loop is for the total number of passes which is N–1. The inner loop will be executed for every pass. However, the frequency of the inner loop will decrease with every pass because after every pass, one element will be in its correct position. Therefore, for every pass, the inner loop will be executed N–I times, where N is the number of elements in the array and I is the count of the pass.
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.
C program for bubble sort
#include<stdio.h>
void main()
{
int i, n, temp, j, arr[10];
printf("\nEnter the number of elements in the array : ");
scanf("%d", &n);
printf("\nEnter the elements: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
for(i=0;i<n;i++)
{
for(j=0; j < n-i-1; j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("\nThe array sorted in ascending order is :\n");
for(i=0;i<n;i++)
{
printf("%d\t", arr[i]);
}
}Output https://onlinegdb.com/Sk1QJc6em
Enter the number of elements in the array : 5
Enter the elements: 11 22 3 5 89
The array sorted in ascending order is :
3 5 11 22 89
You may also like:
Program for insertion sorting in C (With explanation)
If you have any questions related to above article, feel free to ask it in commen't section below.
Buy us a coffee
Become a Patron