Bubble Sort Average Case Analysis

Given Input: [7 8 3 1 6]

 

 

Average Case Analysis

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

1. On the first iteration of the outer loop, while trying to place the largest element, there have to be n - 1 comparisons: the first comparison is made between the first and second elements, the second is made between the second and third elements, and so on until the n-1th comparison is made between the n-1th and the nth element.


2. On the second iteration of the outer loop, there is no need to compare the against the last element of the list, because it was put in the correct place on the previous pass.


3. Therefore, the second iteration requires only n-2 comparisons. This pattern continues until the second-to-last iteration of the outer loop when only the first two elements of the list are unsorted; clearly in this case, only one comparison is necessary.

 

The total number of comparisons, therefore,

(n - 1) + (n - 2)...(2) + (1) = n(n - 1)/2 or O(n²) .

 

Total No of elements : 5

Total No of passes : 5-1 = 4 passes

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

 

Time complexity for Average Case : O(n²)

 

Back...