Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 165 - Project in Algorithms and Data Structures
CS 165 - Project 1 - Testing Running Times
100 points
Please submit your project electronically via EEE Dropbox, with the source code as a single zip file and your report as a single pdf file.
Project 1 involves testing various sorting algorithms experimentally to determine their real-world running times. In particular, you will need to implement each of the following sorting algorithms:
- Bubble-sort
- Insertion-sort
- Spin-the-bottle sort
- Two implementations of Shellsort (using two different gap sequences)
- Two implementations of Annealing sort (using two different temperature-repetition sequences)
For each implementation, you need to perform runtime experiments on random permutations, with multiple runs for each problem size, for increasing problem sizes. Specifically, you need to do a set of experiments for each of the following distributions:
- Uniformly distributed permutations, that is, permutations of the numbers, 1,2,3,...,n, where all permutations are equally likely.
- Almost-sorted permutations. These are generated by starting with a sorted array/vector of n numbers, say, the numbers 1,2,3,...,n, in this order. Then, independently choose 2log n pairs, (i,j), where i and j are uniformly-chosen random integers in the range from 0 to n-1, and swap the numbers at positions i and j in the array/vector.
You must plot the results on a log-log scale (with uniformly distrubted permuations on one plot and almost-sorted permutations on another) to empirically determine the algorithm's asymptotic running time for each type of distribution. You then need to rank all your sorting implementations from asymptotically slowest to fastest based on your experimental results.
In addition, for Shellsort and Annealing sort, you need to test two different sets of parameters that are used by the algorithm, comparing the two to see which one is best. You should experiment with several different parameter sets, so that the final two you use are the two best among many. You should strive to find parameter sets so that one of your Shellsort or Annealing sort implementations is the fastest among all the sorting algorithms you test.
Produce a report write-up that explains the algorithms you implemented, reports on the runtime performance you observed in your experiments, and makes a conclusion regarding which of the set of algorithms you tested is best and why you think it is best.
Turn in your source code (but not test data) as one big zip file, so that when it is unzipped, the code for each algorithm is in a different file, named as follows:
- bubble_sort.cpp
- insertion_sort.cpp
- spin_the_bottle_sort.cpp
- shell_sort.cpp
- annealing_sort.cpp
Turn in your report write-up as one PDF file.