Write the algorithm for bubble sort and explain its worst, best and average cases, precisely?

Bubble Sort:-

In bubble sort method the list is divided into two sub-lists sorted and unsorted. The smallest element is bubbled from unsorted sub-list. After moving the smallest element the imaginary wall moves one element ahead. The bubble sort was originally written to bubble up the highest element in the list. But there is no difference whether highest / lowest element is bubbled. This method is easy to understand but time consuming. In this type, two successive elements are compared and swapping is done. Thus, step-by-step entire array elements are checked. Given a list of ‘n’ elements the bubble sort requires up to n-1 passes to sort the data

Algorithm for Bubble Sort:-

Bubble_Sort ( A [ ] , N )

Step 1 : Repeat For P = 1 to N – 1 Begin

Step 2 : Repeat For J = 1 to N – P Begin

Step 3 : If ( A [ J ] < A [ J – 1 ] )

Swap ( A [ J ] , A [ J – 1 ] ) End For

End For

Step 4 : Exit

Time Complexity of Bubble Sort : -

•  For an array of size n, in the worst case:
• 1st passage through the inner loop: n-1 comparisons and n-1 swaps
• (n-1)st passage through the inner loop: one comparison and one swap.
•  All together: c ((n-1) + (n-2) + ... + 1), where c is the time required to do one comparison,one swap, check the inner loop condition and increment j.

•  We also spend constant time k declaring i,j,temp and initialising i. Outer loop is executed

n-1 times, suppose the cost of checking the loop condition and decrementing i is c1.

c ((n-1) + (n-2) + ... + 1) + k + c1

(n-1) (n-1) + (n-2) + ... + 1 = n(n-1)/2

so our function equals

c n*(n-1)/2 + k + c1(n-1) = 1/2c (n2-n) + c(n-1) + k

Complexity O(n2)

Best case : O (n2)

Average case : O (n2)

Worst case : O (n2)