In class we developed three methods for sorting data (bubble, selection, insertion) and two methods for searching data (linear, binary). When we developed the insertion sort in class, we used a linear type search to determine where the new value to be inserted in the vector should be placed.
Modify the insertion sort to use a binary type search to locate where the new value should be inserted in the vector.
Write a program that will prompt the user to enter the number of values to sort. Your program will populate a vector with that many random values. Copy that data into 2 other vectors so that you have 3 identical vectors.
Sort the first vector using a bubble sort and the second using a selection sort. Using the third vector as the list of values to input, populate a vector using the insertion sort with linear search and another using the binary search.
Using the time() function, display how long it takes to sort the data using the 4 methods.
Run this program several times using the following quantities for the input:
100
1,000
5,000
10,000
50,000
100,000 optional depending on how long the run takes.