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