Bubble Sort is the most straightforward sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. Its worst-case time complexity is high.
begin BubbleSort(list)
for all elements of list
if list[j] > list[j+1]
swap(list[j], list[j+1])
end if
end for
return list
end BubbleSort| Elements | 5 | 20 | 4 | 16 | 2 |
| Index | 0 | 1 | 2 | 3 | 4 |
I have taken an array of length 5 and in this example, we have to sort this array using bubble sort. We have to use a Nested loop for this: -
Here n=5
The Outer loop runs from 0 to n-5 and the Inner loop runs from 0 to n-i-1
On every run, we have to compare the adjacent element and if the first one is greater then swap them.
i=0j=0
| 5 | 20 | 4 | 16 | 2 |
arr[j] = 5, arr[j+1] = 20
5>20 = false, No Swap
j=1
| 5 | 20 | 4 | 16 | 2 |
arr[j] = 20, arr[j+1] = 4
20>4 = true, Swap
j=2
| 5 | 4 | 20 | 16 | 2 |
arr[j] = 20, arr[j+1] = 16
20>16 = true, Swap
j=3
| 5 | 4 | 16 | 20 | 2 |
arr[j] = 20, arr[j+1] = 2
20>2 = true, Swap
Now, the 1st outer loop end, and 20 is at their correct position
| 5 | 4 | 16 | 2 | 20 |
i=1j=0
| 5 | 4 | 16 | 2 |
arr[j] = 5, arr[j+1] = 4
5>4 = true, Swap
j=1
| 4 | 5 | 16 | 2 |
arr[j] = 5, arr[j+1] = 16
5>16 = false, No Swap
j=2
| 4 | 5 | 16 | 2 |
arr[j] = 16, arr[j+1] = 2
16>2 = true, Swap
| 4 | 5 | 2 | 16 |
Now, the 2nd outer loop end, and 16 20 are at their correct position
| 4 | 5 | 2 | 16 | 20 |
i=2j=0
| 4 | 5 | 2 |
arr[j] = 4, arr[j+1] = 5
4>5 = false, No Swap
j=1
| 4 | 5 | 2 |
arr[j] = 5, arr[j+1] = 2
5>2 = true, Swap
| 4 | 2 | 5 |
Now, the 3rd outer loop end, and 5 16 20 are at their correct position
| 4 | 2 | 5 | 16 | 20 |
i=3j=0
| 4 | 2 |
arr[j] = 4, arr[j+1] = 2
4>2 = true, Swap
| 2 | 4 |
Now, the 4th outer loop end, and 2 4 5 16 20 are at their correct position and the array is now sorted.
| 2 | 4 | 5 | 16 | 20 |
#include<stdio.h>
void swap(int *x, int *y){
int temp = *x;
*x = *y;
*y=temp;
}
void printArray(int arr[], int n){
for (int i = 0; i < n; i++){
printf("%d ",arr[i]);
}
}
void main(){
int arr[] = {5,20,4,16,2};
int n=5, i, j, temp;
/*
Bubble Sort
Here number of elements is 5
*/
// Outer loop
for(i=0;i<n-1;i++){
// Inner loop
for (j = 0; j < n-i-1; j++){
/*
Comparing arr[j+1] with arr[j] (Two adjacent elements)
And swap them if arr[j] is greater
*/
if(arr[j+1]<arr[j]){
// Swap
swap(&arr[j], &arr[j+1]);
}
}
}
// Printing the array
printArray(arr, n);
}