Home Arrays Bubble Sort

Bubble Sort

by nikoo28
0 comment

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.

Single iteration of bubble sort
Fig: Single iteration of bubble sort

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 end

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; }

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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More