CS 300 Project 2 For the project, you will work in teams of 2. Each person must write 2 of the sort algorithms for the project. You need to let me know who you are working with. At the top of the sort algorithms, the name of the person writing it should be stated. Both names should be in the main.cpp. You will write the following sorts: Selection sort Straight insertion sort Bubble sort Quick sort You are to find a C++ implementation of the shell sort on the internet and use it also. The efficiency for shell sort is Big-O (n1.25). You will need to modify the shell sort to count operations. In addition to the sorts, you will write the binary search tree to insert the data and print it out inorder. You are to generate three unsorted lists of data of different sizes: 50, 5000, and 100,000 items in your program. The unsorted lists will consist of a data structure that contains the key (an integer), and a random string. Both the key and the string are to be randomly generated. You may determine how to generate the random string. There should be at least 5 different strings used. This is so that you will be using a structure rather than just a single piece of data. Put the structure into an array and sort each array by the key using the 5 different sorts. For each array, you are to determine the Big-O value for each sort for each data size. This is to be calculated using the Big-O values given in class and printed out as part of your data. The point here is for you to use the numbers of the array sizes and show what the numbers would be based on the average Big-O values given in class. Be sure that you start with the same dataset for each sort. In the sorting routines, you are to calculate the number of operations (estimated like Big-O) it takes for each sort. For each of your sorts, you need to print the sorted output to a file called AAAXXX.txt where AAA is 3 identifying letters for type of sort and XXX is the size of the sort. You will also use the same data to insert into a binary tree and use the in-order traversal. Again you are to keep track of the number of operations. You should print in-order traversal to file bstxxx.dat where xxx is the dataset size. The number of operations should be calculated for each dataset. Along with your calculated Big-O values for each sort, you should show the number of operations it takes for each sort to be performed. The calculations should all be printed to a file called sortinfo.txt. For each of the sort algorithms, you are to take the sorted 5000 dataset and run it through the sort algorithm. Show the number of operations for each sort when the data is already sorted. This information will be added to the sortinfo.txt file. Analyze the data and explain your results. Does the actual count agree with your calculations? Which sort is faster? Does the data size make a difference? This information should be put in a file called analyze.txt. It should be about a paragraph. For example: List 50 Big O calculated value selection sort: O(n2 ) = 250 Big O calculated value insert sort: ____ Big O calculated value bubble sort: ____ Big O calculated value quick sort: ____ Big O calculated value shell sort: ____ Big O calculated value bst: ____ Selection sort operations: ____ Straight insertion sort operations: ____ Bubble sort operations: _____ Quick sort operations: _____ Shell sort operations: _____ Binary search tree operations: _____ Name the files selection.cpp, insertion.cpp, bubble.cpp, quick.cpp, bst.cpp, shell.cpp, and main.cpp. Supply a makefile for your project. Supply any needed .hpp files. Turn in the datasets that you generated to be sorted. Only 1 member of the team is to turn in your project, but be sure both names and WSU ids are in the comments at the top of the main.cpp file. Use ~cs300d/bin/handin project2 to turn in your project.