This question uses known comparison-count formulas to compare the efficiency of a bubble sort and a quicksort as the size of the list, n, grows large.
(a)The number of comparisons made by a bubble sort in the worst case, on a list of n items, is given by n(n - 1)/2. Calculate the worst-case number of comparisons for (i) n = 50, (ii) n = 200, (iii) n = 1024.(3)
(b)Given that n increased by a factor of 4 between parts (a)(i) and (a)(ii), show that the ratio of your two answers is consistent with the bubble sort's worst-case order of O(n2).(2)
(c)A quicksort, on average, makes approximately n log2(n) comparisons to sort a list of n items. Calculate the approximate number of comparisons a quicksort would make, on average, to sort a list of n = 1024 items.(2)
(d)By comparing your answer to part (c) with your answer to part (a)(iii), comment on the practical significance, for large n, of the difference in order between an O(n log n) algorithm and an O(n2) algorithm.(2)