Bubble Sort

Bubble sort is a comparison based algorithm. The bubble sort works by comparing each item in the list with the item next to it and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items

Example:

consider list : 2,9,5,4,1,3

The number of comparisons made at each of the iterations is as follows:

(n - 1) comparisons in the first iteration, (n - 2) comparisons in the second iteration, ... , one comparison in the last iteration. Thus, the total number of comparisons is n(n - 1)/2, which is O(n²).

Hence, the time complexity for each of the cases is given by the following:

1. Average case complexity = O(n²)

2. Best case complexity = O(n²)

3. Worst case complexity = O(n²)