Write a C++ program called performance.cpp that displays the performance of three different sorting algorithms (selection sort, insertion sort, and quick sort) on the screen.

Your program should read the input size (= number of input data) from a user and generate the input data (= positive integer numbers) based on the users selection (= numbers in the ascending order, numbers in the descending order, or numbers in the random order). Your program can generate any positive numbers. However, you have to generate the numbers in the correct order (= ascending, descending, or random) to meet the users choice. For the homework, your program should save the input data to a file named input.txt on the clould9 so that you can check the content of the input data later when you finish the execution. We will also check the file content when we grade your program.

Once your program generates the input data, it should conduct the sorting algorithms for the input file and display execution time information (= start time, end time, and elapsed time) for each sorting algorithm. In the problem, you should use dynamic memory to hold a big input size such as 10,000, 50,000 or more. For the homework, you have to implement the pseudocode presented in our textbook. If you use a library function for the sorting, you will not get the credit for the homework. This is the list of sorting algorithms in our textbook:

1. Selection Sort Page 99.

2. Insertion Sort Page 134

3. Quick Sort Page 176 & 178

This is a sample result of the C++ program on the cloud9:

$ g++ -o performance performance.cpp

$ ./performance

Enter input size: 350

========== Select Order of Input Numbers ==========

1. Ascending Order

2. Descending Order

3. Random Order

Choose order: 1

============================================================

Generate input data in ascending order . . .

Done.

============================================================

============================================================

Selection sort performance

Starting time: 2018-5-22 23:04:38 // Its a just sample time.

Ending time: 2018-5-22 23:04:40 // Actual time will be different.

Elapsed time: 2.40925 seconds // Elapsed time can be an integer

// second such as 2 seconds

============================================================

============================================================

Insertion sort performance

Starting time: 2018-5-22 23:04:41

Ending time: 2018-5-22 23:04:41

Elapsed time: 0.21503 seconds

============================================================

============================================================

Quicksort performance

Starting time: 2018-5-22 23:04:42

Ending time: 2018-5-22 23:04:43

Elapsed time: 1.477957 seconds

============================================================

In the sample execution, your program should generate 350 integer numbers in the file named input.txt on the cloud9. The data in the file should be in the ascending order because the user selected that option. If you want to see the content of the file, you can use the cat command as below:

$ cat input.txt

1 2 3 4 5 6 7 ... // It will display all 350 positive integer

// numbers on the screen.

For the homework, you can display the elapsed time in integer seconds. However, if you want, you can also display it in milliseconds for more accurate measurement. Additionally, note that the time information on the sample run is not an actual execution time. It was just entered by the instructor without any consideration. When you display the time, exclude the time to generate the input file and read the input file. You have to measure only the sorting time.

This is another sample result:

$ g++ -o performance performance.cpp

$ ./performance

Enter input size: 50000

========== Select Order of Input Numbers ==========

1. Ascending Order

2. Descending Order

3. Random Order

Choose order: 3

============================================================

Generate input data in random order . . .

Done.

============================================================

============================================================

Selection sort performance

Starting time: 2018-5-22 23:04:39

Ending time: 2018-5-22 23:04:40

Elapsed time: 1.40925 seconds

============================================================

============================================================

Insertion sort performance

Starting time: 2018-5-22 23:04:41

Ending time: 2018-5-22 23:04:41

Elapsed time: 0.21503 seconds

============================================================

============================================================

Quicksort performance

Starting time: 2018-5-22 23:04:42

Ending time: 2018-5-22 23:04:43

Elapsed time: 1.477957 seconds

============================================================

In this sample execution, your program should generate 50,000 positive integer numbers in the file named input.txt. This is an example

$ cat input.txt

5 320 23 900 4397 ... // It will display all 50000 numbers

// on the screen.