undefined

Part 1: Naive Solution Write a simple program that will generate input lists of n = 1,000, n = 10,000, and n = 1,00,000 unique integers and a value k which the position where the kth smallest value is to be found. Write a sorting algorithm that will permute the input into an in- creasing list and then select the kth smallest value. I suggest using Quicksort as described by Hoare 5 and Bentley, but leave the choice of sort algorithm to you. Analysis What is the big-O behavior of your sort and select program? Use Excel to create a line chart showing the run-time on the the three inputs n = 1,000, n = 10,000, and n = 1,00,000. Show the trend lines and R-squared values on your chart. Does your empirical data agree with your big-0 analysis? Part 2: A Smarter Solution Implement the select algorithm described by Bentley, or Hoare, or the Corman et. al. textbook. Analysis Perform the same analysis for this program as described in the previ- ous section for part 1. What is the speed-up in execution time compared to program 1