Harvard University Lower Bounds and Linear Time Sorting Questionnaire

Question 6: Lower Bounds and Linear time Sorting• (a) A set of n natural numbers are uniformly distributed in the range 1 < x < Vn. Determine the runtime (in big-Theta notation) of Counting Sort and Radix Sort. Find the expected runtime of Bucket sort using 10 buckets. Which algorithm has the best asymptotic runtime? (b) Given a set of three numbers {a,b,c} draw the comparison-based decision tree that represents the execution of bubble-sort. Justify the length of the longest-path in your tree, using the results of problem 5 from practice set 1. 4 Figure for problem lc: Below shows one step of the girls sorting process. Examining bears 5 and 1, she decides they need to be swapped. Then she moves left and will examine bears 4 and 1 next. Problem 5: You may have already come across another simple sorting algorithm called Bubble-sort. Instead of describing the algorithm here, you are asked to do a bit of online research. One great place to start is here: https://www.youtube.com/watch?v=lyZQP JUT5B4 Write the basic pseudo-code for Bubble sort, using comparisons and swaps. Determine the worst-case number of swaps and the worst-case number of comparisons. Repeat for the best-case. Problem 5 Assume that the input to Bubble sort is an array A indexed from 1 to n. The algorithm below passes through the elements of the array and swaps any two adjacent elements that are not in relative order. The process continues until a full pass can be made without any swaps. made-swap = true while(made-swap) made-swap = false for i = 1 to n-1 if A[i+1] < A[i] Swap A[i] and A[i+1] made-swap = true Worst-case: Note that in the above algorithm, each execution of the for-loop carries out exactly n-1 comparisons. If the array is sorted in reverse order, then after each pass of Bubblesort the maximum element of the unsorted section is moved into the last position. For example, starting with 5, 4, 3, 2, 1 after one pass of bubble-sort the array becomes: 4,3,2,1,5, and after the second pass the array becomes 3, 2, 1,4,5. Each pass places exactly one element in its final sorted position, and therefore n passes are needed. Each pass performs exactly n 1 comparisons, and therefore the worst-case number of comparisons is n(n-1). The number of swaps made during the first pass is n-1, during the second is n-2, etc. Therefore the total number of swaps is n(n-1)/2 in the worst case. Best-case: Bubblesort is effective if it is given an array that is already sorted. It is able to detect this right away, and return the sorted array after one pass. This is because on a sorted array, 1, 2, 3, 4, 5, Bubblesort performs no swaps on the first pass, and therefore will not repeat a second pass. Therefore the best-case number of swaps is 0 and the best-case number of comparisons is n - 1.