Bubble sort is a popular sorting algorithm that we prefer to sort the components of an array in a clear and particular order. Essentially, in this algorithm, we need to compare the two adjacent elements and perform a swap operation on them until they do not come in the planned order.
If the positions of the components are right, then we have to move to the next iteration; else, we need to perform a swap strategy.
Here, we will learn the bubble sort algorithm. This article will be very helpful for you and provide you with in-depth knowledge about this algorithm.
- Bubble Sort Algorithm
- Working of Bubble Sort Algorithm
- Bubble Sort Complexity
- Time Complexity
- Space Complexity
- Program Implementation of Bubble Sort
Bubble Sort Algorithm
Let’s assume that arr is an array with n members (elements):
- begin BubbleSort(arr)
- for all array elements
- if arr[i] > arr[i+1]
- swap(arr[i], arr[i+1])
- end if
- end for
- return arr
- end BubbleSort
Working of Bubble Sort Algorithm
Let’s now examine how bubble sort algorithms function.
We are using an unsorted array to better understand how the bubble sort algorithm operates.
Let the array’s components be:
First Pass:
Starting with the first two components, we’ll sort. To determine which component is greater, we shall compare them.
In this case, 31 is greater than 12 (31 > 12), hence nothing needs to be done because these components are already sorted. It’s time to compare 31 to 25 at this point.
25 is less than 31 here. This calls for a swap operation to be made. The new array will be obtained after the swap:
Now, we will compare 31 and 34.
34 is higher than 31 in this case. Since these components are already sorted, there is no need for swap operations in this situation.
Now, we will compare the two elements 34 and 9.
In this case, 9 is less than 34. None of these components are sorted. Therefore, we must do a swap operation. We have now reached the end of the array. As a result, here is how the array appears following the first pass:
Now, we have to think about the second iteration.
Second Pass
We’ll proceed in the same way as we did during the first pass likewise here.
9 is less than 31 here. As a result, we must exchange here. The new array appears as follows:
We are moving to the third iteration now.
Third Pass
We will proceed in the same manner that we did in the first and second passes likewise here.
9 is less than 25 here. We must do a swap operation, and the outcome is as follows:
Now, we are moving to the fourth iteration.
Fourth pass
So, after the fourth iteration, this is how the array will look.
As a result, there is no swap procedure required in this situation. Now that the array is sorted.
Bubble Sort Complexity
One of the most trustworthy sorting algorithms is bubble sort. Here, we’ll talk about the three time complexity case studies. Best, typical, and worst case scenarios.
1. Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
2. Space Complexity
| Space Complexity | O(1) |
|---|
Program: Write a program to implement bubble sort in C language.
#include<stdio.h>
void print(int p[], int q) //function to print array elements
{
int r;
for(r = 0; r <q; r++)
{
printf(“%d “,p[r]);
}
}
void bubble(int p[], int q) // function to execute bubble sort
{
int r, s, temp;
for(r = 0; r < q; r++)
{
for(s= r+1; s < q; s++)
{
if(a[s] < a[r])
{
temp = a[r];
a[r] = a[s];
a[s] = temp;
}
}
}
}
void main ()
{
int r, s,temp;
int a[5] = { 9, 34, 31, 11, 25};
int p = sizeof(a)/sizeof(a[0]);
printf(“Before organizing array components are – \n”);
print(p, q);
bubble(p, q);
printf(“\nAfter sorting array elements are – \n”);
print(p, q);
}
Output
Before sorting array elements are-
9,34,32,12,26
After sorting array elements are –
9, 12, 25,31,34
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
