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