Algorithm 1 Bubble Sort 1: input: A list L of n real numbers 2: for Each element r E L from L(2) to L(n) do 3: while r is less than the element preceding a in L do 4: swap that element with 5: end while 6: end for 7: return The sorted list L Question 4: (40 points) Given a list of n distinct real numbers, a sorting algorithm seeks to reorder the list from smallest to largest. As comparisons between elements are relatively slow, sorting algorithms are commonly judged by the number of comparisons they make. Algorithm 1 is called bubble sort because each element in turn "bubbles" up through the sorted part of the list to its proper place. We also provide a Python implementation of the bubble sort algorithm. a) Compute the marimum possible number of comparisons between list elements made by the deterministic bubble sort in Algorithm 1, in terms of n. b) To avoid the worst case, randomized bubble sort first randomly permutes the list, and then runs bubble sort. Let X be an integer random variable equal to the number of comparisons made by randomized bubble sort. Compute E[X] in terms of n. c) Monte Carlo sampling can be used to estimate the cumulative distribution function of X. Use Python to execute the provided randomizedBubbleSort 1000 times for lists of length n = 10, and plot the empirical CDF Fx(x). Compute and report the average number of comparisons across your 1000 Monte Carlo trials. d) Repeat part (c) for lists of length n = 100, and discuss how the distribution of comparisons changes as the list length grows