Due at the end of lab.

This lab you need to calculate some runtime data for the code from the previous lab. This will require extending the code from the previous lab. Specifically you need to do the following:

• Read in the data file namedata.txt, which contains the 2000 most common baby names in the U.S. from 1880.
• Search for a given name and report whether or not it's in the list
• Repeat the search at least 20 times with different names from the list and report the average number of comparisons (e.g. commands like if(names[i] == target)) required to find a name.
• Sort the entire list alphabetically. Report how many comparisons (e.g. commands like if(names[i] > names[i+1])) where required to sort the list.
• Write another function that searches the sorted array using a binary search algorithm (last week's extra credit).
• Search the sorted list using the binary search at least 20 times with different names from the list and report the average number of comparisons (e.g. commands like if(names[i] == target)) required to find a name.

To read in the names you will need to create an ifstream object (ifstream stands for "input file stream") and connect it to the namedata.txt file. The names can be stored in an array of stings (of size 2000).

The searchs should each be done by a separate function that recieves three arguments: the array, the size of the array, and the string/name to search for. The function should return -1 if the name is not in the array and the location of the name (a number between 0 and 1999) if the name is in the array. The main() function should print the message saying whether or not the name is present and it's location if it is present.

There should be a separate function to sort the array. This function should take two arguments, the array and the size of the array.

Extra Credit:

Turn in: Your code and sample output. Use a text editor to add to the end of the sample output the average time to search the unsorted list and to search the sorted list.