IST238: Algorithms. Project #2.

In this project you need to implement different versions of the step sequence for the Shell sort algorithm. The sequences you need to implement are
  1. 1 4 13 40 121 364 1093 3280 9841 ... (ai = 3*ai-1+1)
  2. 1 2 4 8 16 32 64 128 256 512 ... (ai = 2i-1)
  3. 1 8 23 77 281 1073 4193 ... (ai = 4i+1+3*2i+1)
  4. {  αi  }, where   x   is the largest integer less than or equal to x. For this sequence you first need find the best α. In other words, you need to sort the same array using this sequence generated by different floating point numbers and choose the one produces the fastest result.
As the result of the project you should submit:
  1. file shell_sort.cpp
  2. a table with the run times for N = 10000, 20000, 40000 for each sequence you tested and also your prediction for 80000 and the real runtime for N = 80000 (for each sequence of'course).

For additional credits you can implement the Pratt's sequence ("triangle sequence").