Code in Python:

Suppose you have a group of N integer numbers, and you would like to determine the kth largest number. Write a program to solve this selection problem. Also estimate how much CPU time is used to solve the problem. Consider solving this problem this way:

read from input file the following data o valueofN,

o valueofk|0<k<=N,

o andNnumbersintoadynamicarray,

sort the array in decreasing order via bubble sort, print the sorted array to an output file

and then find the array element at index k-1, print it to the output file also

Objective

learn input/output from/to files

learn how to estimate CPU time that is used by your program

learn sorting

Detailed Algorithm

t1 = current CPU time in nanoseconds

Read data (N, k, N integers) from in.txt input file to variables and to a dynamic array of size N

t2 = current CPU time in nanoseconds

Bubble sort the array

Find kth largest element

t3 = current CPU time in nanoseconds

Output (print) the sorted array and kth largest element to an output file

t4 = current CPU time in nanoseconds

Print statistics to the same output file

o print CPU time used during input (di=t2-t1) o print CPU time used during calculations (dc=t3-t2) o print CPU time used during output (do=t4-t3)

Input and Output Files

In the description below, bold text has to be used as-is. Actual values have to be used instead of cursive text. Input file

Input file must be named in.txt and must have the following format Nk

integer1 integer2 ... integerN The first line must contain two numbers value of N and value of k.

The second line must contain N integer numbers. Numbers must be separated by whitespaces. Note that the input file must not have ..., actual numbers must be used instead.

Output file

Output file must be named out.txt and must have the following format

sorted1 sorted2 ... sortedN kth largest is X CPU time used during input = di nanoseconds CPU time used during calculations = dc nanoseconds CPU time used during output = do nanoseconds

The first line must contain sorted array elements in descending order, separated by whitespaces. Note that ... must not be printed, actual array element must be printed instead.

The second line must contain string literals as specified above with actual values substituted for k and X. The last 3 lines must contain string literals as specified above with actual values substituted for di, dc, and do.

Example

Use this example to test your program in.txt content

85 6 8 10 3 2 1 11 13

out.txt content

13 11 10 8 6 3 2 1 5th largest is 6 CPU time used during input = di nanoseconds CPU time used during calculations = dc nanoseconds CPU time used during output = do nanoseconds