The bubble sort algorithm can be terminated if at any point

The bubble sort algorithm can be terminated if at any point in the execution of the algorithm, no exchanges are made through the unsorted part of the list (i.e, the list is then already sorted).

• Modify the bubblesort algorithm (the textbook’s algorithm) to include this optimization. Write down the modified algorithm

//Sorts a given array by bubble sort

//Input: An array A[0..n 1] of orderable elements
//Output: Array A[0..n 1] sorted in nondecreasing order
for i 0 to n 2 do
for j 0 to n 2 i do
if A[j + 1]<A[j ] swap A[j ] and A[j + 1]

What is the big Oh complexity of the algorithm with this optimization? Justify

Solution

the cases for bubble sort for posible algorithm will be like as given below

1) O(n) (Best case condition) This time complexity can occur if the array is already in sorted, and that means that no swap occurred and only 1 iteration of n elements

2) O(n^2) (Worst case condition) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end or at the last of array ) and so on and so forth till 1 comparison occurs.

Big Oh = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

in this algorith it may not examine these many elements in each phase as the array is not in descending order. hence optimization may not help that much