Please read the remarks about programming problems for this course.

In class we talked about the problem of finding the k^th largest element from a collection of n elements. This is called the selection problem.

Write a C++ program that solves the selection problem involving integers in two different ways:

• Sort and select.
  1. Read all the integer elements into an array or vector.
  2. Sort the array or vector into descending order.
  3. Select the k^th largest element from the sorted collection; that is, the element at index k - 1 within the sorted collection. The first largest element (k = 1) is at index zero, the second largest element (k = 2) is at index one, etc.
• Partial sort and insert.
  1. Read the first k integer elements into an array or vector.
  2. Sort the array or vector into descending order.
  3. Read each remaining element one at a time:
     • Ignore the element if it is less than the k^th element in the array or vector, or
     • Insert the element into its proper place in the array or vector, displacing one existing element from the array or vector. The array or vector always should contain k elements.
  4. Select the k^th largest element from the sorted collection; that is, the last element (index k - 1) within the sorted collection.

1. Provide two different implementations (functions) based on the two descriptions above. The prototypes of the functions are
   • select_kth_largest1(std::istream& in);
   • select_kth_largest2(std::istream& in);
   The parameter is a std::istream reference. The std::istream class is the base class for std::ifstream, so the functions will accept a std::ifstream input file stream object as well as the familiar std::cin keyboard std::istream object. The following shows some example calling code:

           ifstream fin("100.data");
           if (fin.good()) {
               cout << select_kth_largest1(fin) << endl;
               fin.close();
           }
           

   The functions read in the file contents and return the k^th largest element in the sequence.

   Use the same sorting algorithm for both implementations. You may use the std::sort function if you like. If arr is an array containing n elements, the call std::sort(arr, arr + n, greater<int>()) sorts the array in descending order.

2. Your program should get its input from a text file. The format of the file is N k n1 n2 n3 ..., where
   • N is the number of integers to be considered
   • k corresponds to k in the problem.
   • n1, n2, n3, ... is the sequence of integers; there will be N of these. The list contains no duplicates.
   For example, if the data file contains

            5 3 25 3 14 30 8
            

   the sequence of integers would be 25, 3, 14, 30, 8, and the 3rd largest element is 14.

   The select_kth_largest1 and select_kth_largest2 functions are responsible for reading the contents of the files via their istream& parameter.

3. Your program should output two numbers: the kth largest element in the data set as determined by the two different functions. Your program should produce no other output.

   For this assignment you need not worry about malformed data files.

   You may use the sample inputs found here. You'll see in one file the sample input has 100 integers, and you are looking for the 24th largest integer. In another file you will find the 130th largest element amongst 1,000. In a third file you will find the 50,000th largest element in a sequence of 100,000 integers.

4. In Excel or Word produce a table comparing the running times of both implementations on sequences of sizes 100, 1000, and 100000.

   You may use a Stopwatch object as described in Section 16.2 of the CPTR 124 textbook to time the execution of the functions. This means for testing purposes you can add printing statements temporarily to harvest timing information.