# 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)