Solve the following problems 4 The bubble sort algorithm can

Solve the following problems:

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

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

Solution

def shortBubbleSort(alist):
exchanges = True
passnum = len(alist)-1
while passnum > 0 and exchanges:
exchanges = False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchanges = True
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum = passnum-1

alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)

# above is python code

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

Case 2) O(n^2) (Worst case) 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) 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)

So aymptotic complexity even after optimization is still O(n^2) .

consider following example

You go up to your friend and say, \"I have an amount of money in my pocket, and I guarantee that it\'s no more than one million dollars.\" Your statement is absolutely true, though not terribly precise. One million dollars is an upper bound on 10 dollars, just as O(n^2) is an upper bound on the running time of bubble sort .

But (n^2) would not be correct to describe the running time of bubbe sort because it does not always run in n^2 since its best case is o(n).

answer: O(n^2) .