School of Computing and Mathematical Sciences The following algorithm, bubblesort, sorts a list of n integers into increasing order by successively comparing adjacent elements and interchanging them...

Question is on discrete mathematics for computer science it can be viewed by checking out the pdf


School of Computing and Mathematical Sciences The following algorithm, bubblesort, sorts a list of n integers into increasing order by successively comparing adjacent elements and interchanging them if they are in the wrong order. Input x1, x2, x3, …, xn ; begin for i := 1 to (n – 1) do for j := 1 to (n - i) do if xj > xj+1 then begin temp:= xj ; xj := xj+1 ; xj+1 := temp ; end else {do-nothing}; end Output x1, x2, x3, …, xn ; (a) When n = 4, trace the values of i, j, x1, x2, x3 and x4 for the input values x1 = 3, x2 = 2, x3 = 7, x4 =1. (4 marks) (b) A time complexity function T(n) can be found for bubblesort by counting the number of times the comparison jx > 1jx  is made for a general positive input n. Show that T(n) is  2O n . (4 marks) (c) Another sorting algorithm requires 2 3 log n n comparisons to sort a list of n integers into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer. (2 marks) Question 7