Bubble sort is one of the simplest sorting algorithms and it works on the principle of swapping two elements. Think of the bubble sort as a water bubble that arises from the bottom of the ocean. As it rises up, it grows in size and its the maximum when it reaches the surface.
Similarly, in bubble sort, we arrange items from smallest to the largest at the end one by one in each iteration.
The algorithm for bubble sort is as follows:-
- We start from the bottom of the array and look for smaller elements.
- Select the last element.
- If the second last element is greater than the selected number, swap both of them.
- Now compare the second last number with the third last number. If the number is not small, then do not swap, else again swap.
- This way by swapping each time, we will get the smallest number in the array and it will bubble at the top of the array.
- In the second iteration compare till the second position in the array.
- In the third iteration, compare till the third position in the array and so on.
The image shows a single iteration on an unsorted array. Note that after the iteration is complete, the smallest element has bubbled towards the first position.
The algorithm for the above code can be given as:-
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
break if not swapped
endCode language: plaintext (plaintext)An implementation of the algorithm in C can be done as:
#include<stdio.h>;
// function to swap two integers
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
//defining a function to perform bubble sort on array arr[] of given size
void bubbleSort(int arr[], int size)
{
int i,j;
for(i = 0; i < size; i++)
{
// a variable to see if any element was swapped
int swapped = 0;
// starting with the last element
for(j = size - 1; j > i; j--)
{
//comparing if the element is smaller than the previous one
if(arr[j] < arr[j-1])
{
//if true, then we swap them and change the flag
swap(&arr[j], &arr[j-1]);
swapped = 1;
}
}
// if no element was swapped, that means the array was sorted
// and we do not need to perform any additional loops
if(swapped == 0)
break;
}
}
// driver program to test the above function
int main(void)
{
int i;
int arr[10] = {3, 4, 7, 1, 10, 8, 2, 22, 99, 50};
bubbleSort(arr,10);
printf("SORTED array:- ");
for(i = 0; i < 10; i++)
printf("%d ", arr[i]);
return 0;
}
Code language: C/AL (cal)Time Complexity: O(n^2)
Space Complexity: O(1)
Fun Fact: This sorting algorithm works better in a case when your array is nearly sorted. You can also note that this method will perform a maximum of O(n) swaps. Hence, it is useful in a scenario when your cost of swapping elements is very high.
Video Explanation:
Check out this video explanation where I show you a different example of bubble sort. The largest element bubbles towards the end after each iteration.
