Bubble Sort Worst Case Analysis

 

Given Input: [ 8 7 6 3 1]

 

Worst Case Analysis

****************

 

1. The absolute worst case for bubble sort is when the smallest element of the list is at the large end.


2. Because in each iteration only the largest unsorted element gets put in its proper location, when the smallest element is at the end, it will have to be swapped each time through the list, and it wont get to the front of the list until all n iterations have occurred.


3. In this worst case, it take n iterations of n/2 swaps

 

Total No of elements : 5

 

Total No of passes : 5-1 = 4 passes

 

Also smallest element 1 is placed in last position , so to place 1 in first position , it needs n iterations.

 

For all the passes , bubble sort takes 10 comparisons in worst case analysis.

 

Time complexity for Best Case : O(n²)

 

Back..