IST238: Algorithms. Project #1.

In this project you need to implement two versions of the Insertion sort algorithm. The first version should perform the linear search in order to find the right place for the first element from the data portion of the array, while the second version is to execute the binary search to locate this place. More precisely, you should do the following:
  1. Implement the Insertion sort with linear search.
  2. Run the program for random array of the size 10000, 20000, and 40000.
  3. Forecast the runtime for N = 80000, then run the program and check.
  4. Make your predictions about the runtime for N = 800,000
  5. Implement the Insertion sort with binary search.
  6. Run the program for random array of the size 10000, 20000, and 40000.
  7. Forecast the runtime for N = 80000, then run the program and check.
  8. Compare the speed of the two versions of the algorithm.
  9. Make your predictions about the runtime for N = 800,000
As the result of the project you should submit:
  1. file lin_ins_sort.cpp (with the linear search)
  2. file bin_ins_sort.cpp (with the binary search)
  3. a table with the run times for N = 10000, 20000, 40000, your prediction for 80000 and the real runtime for N = 80000, don't forget your forecast for N = 800000.