#### What is bubble sort?

An in-place sorting algorithm that finds max. element in each cycle and puts it in appropriate position in list by performing swapping adjacent elements. In bubble sort, we continue swapping adjacent elements until they are in correct order.

As we need to iterate the whole array for every element, the complexity of this algorithm is O(n^2).

#### Time and Space Complexity:

• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)
• Best Space Complexity: O(1)

#### Steps to implement bubble sort:

1. In first cycle,
1. Start by comparing 1st and 2nd element and swap if 1st element is greater.
2. After that do the same for 2nd and 3rd element.
3. At the end of cycle you will get max element at the end of list.
2. Now do the same in all subsequent cycles.
3. Perform this for (number of elements – 1) times.
4. You will get sorted list.

#### Pseudo code for bubble sort:

```Initialize n = Length of Array

BubbleSort(Array, n)
{
for i = 0 to n-2
{
for j = 0 to n-2
{
if Array[j] > Array[j+1]
{
swap(Array[j], Array[j+1])
}
}
}
}```