algorithm

Bubble Sort Algorithm

Bubble Sort : Overview

  • Bubble sort is considered the simplest sorting algorithm.
  • Bubble Sort is used to sort a given set of n elements provided in form of an array with n number of elements.
  • Bubble Sort compares all the element one by one and sort them based on their values.
  • It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.
  • Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.

Implementing Bubble Sort Algorithm

  • Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array.
  • Step 2: If the current element is greater than the next element of the array, swap them.
  • Step 3: If the current element is less than the next element, move to the next element.
  • Step 4: Repeat Step 1.

Complexity Analysis of Bubble Sort Algorithm

In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,

(n-1) + (n-2) + (n-3) + (n-4) + (n-5) + ….. + 3 + 2 + 1

Sum = n(n-1)/2

i.e O(n2)

  • Time complexity of Bubble Sort is O(n2).
  • The main advantage of Bubble Sort is the simplicity of the algorithm.
  • The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable.
  • Also, the best case time complexity will be O(n), it is when the list is already sorted.

Following are the Time and Space complexity for the Bubble Sort algorithm.

  • Worst Case Time Complexity [ Big-O ]: O(n2)
  • Best Case Time Complexity [Big-omega]: O(n)
  • Average Time Complexity [Big-theta]: O(n2)
  • Space Complexity: O(1)

 

Leave a Reply