Bubble Sort

Is one of the simplest sorting algorithms.
Has a quadratic order of growth and is therefore suitable for sorting small lists only.
Works by repeatedly scanning through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

Algorithm for bubble sort:

1.	Set pass = 1.
2.	Repeat step 3 varying j from 0 to n – 1- pass. 
3.	If the element at index j is greater than 
the element at index j + 1, swap the two elements.
4.	Increment pass by 1.
5.	If pass <= n – 1, go to step 2.

Determining the Efficiency of the Bubble Sort Algorithm

The efficiency of a sorting algorithm is measured in terms of number of comparisons.
There are n-1 comparisons in Pass 1, n-2 comparisons in Pass 2, and so on.
The total number of comparisons will be calculated by using the following formula:

Sum = (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1

Sum = n/2 [2a + (n – 1)d]

Sum = (n – 1)/2 [2 × 1 + (n – 1 – 1) × 1]

Sum = (n – 1)/2 [2 + (n – 2)]

Sum = (n – 1)/2 (n)

Sum = n(n – 1)/2

The bubble sort algorithm is of the order O(n2).