[Solved] CH08-320201-Homework 6 Sorting in Linear Time and Radix Sort

Problem 1: Sorting in Linear Time

• Given the sequence < 9,1,6,7,6,2,1 >, sort the sequence by Counting Sort.
• Given the sequence < 0.9,0.1,0.6,0.7,0.6,0.2,0.1 >, sort the sequence by Bucket Sort.
• Given n integers in the range 0 to k, design an algorithm (only pseudocode) with pre-processing time Θ(n + k) that counts in O(1) how many of the integers fall into the interval [a,b].
• Given a sequence of n English words of length k, implement an algorithm that sorts them in Θ(n). Let k and n be flexible, i.e., automatically determined when reading the input sequence.
• Given any input sequence of length n, determine the worst-case time complexity for Bucket Sort. Explain your answer!
• Given n 2D points that are uniformly randomly distributed within the unit circle, design an algorithm (only pseudocode) that sorts the points by increasing Euclidean distance to the circle’s origin.

Problem 2: Radix Sort

Consider Hollerith’s version of the Radix Sort, i.e., a Radix Sort that starts with the most significant bit and propagates iteratively to the least significant bit (instead of vice versa).

• Implement Hollerith’s version of the Radix Sort.
• Derive the asymptotic time complexity and the asymptotic storage space required for your implementation.
• * Show how to sort n integers in the range 0 to n³− 1 in O(n)