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.