You are to evaluate the sorting times for five sorting algorithms. The five algorithms are:
1) Heap sort
2) Quick sort
3) Selection sort
4) Exchange Sort version 1
5) Exchange Sort version 2
The task is to sort an array of integers. Your code will be written in the provided Sort-Main.cpp file. The following are the parameters of the experiment:
1) Before each sort, the array to be sorted is initialized with random integers. To initialize random integers in array x of length y, use the function void randomFill(int x[], int y); provided in the Sort-Main.cpp file.
2) There will be three array sizes to sort. The sizes are 16384, 32768, and 65536.
3) For each sorting algorithm and array size combination, there will be 10 sorts performed. The time for each sort will be measured. The time of the 10 sorts for each sorting algorithm and array size combination will be averaged and captured. You should write your code to perform this operation.
4) Do not use any input or output functions (e.g. std::cout) when measuring the time of a sort. You can output items while testing your code, but the final measurements have to be performed with no output to the display while sorting, otherwise the measured time could be negatively impacted.
5) To measure the time of each sort, use the Timer class in the provided Timer.h file. At the top of the Sort-Main.cpp file, a timer object t is created. Use this for the measurements. Right before the sorting starts (do not include initializing the array with random numbers), invoke the t.markTime() function. When the sorting has completed, invoke the time1 = t.getTime(); function. The sorting time will be contained in the time1 variable in seconds.
6) The heap sort algorithm is provided in the STL. Use the std::make_heap() command followed by the std::sort_heap(); command to complete the sorting.
7) The quick sort algorithm is provided in the STL. Use the std::sort() command to perform the sorting.
8) The Selection sort, Exchange sort version 1, and Exchange sort version 2 algorithms are provided in the sorting.cpp and sorting.h files, which are provided for you. Note: the exchange sort version 2 may take up to 60 seconds to complete one sort.
Evaluation of algorithms:
1) Record all the average times in an excel spreadsheet. There should be 15 times captured (5 algorithms and 3 array sizes combinations). Make sure the times are labeled so they can be correctly identified.
2) Capture your analysis in a word file. In your analysis you should include:
a) Analysis of the change in times for each array size. Focus on the ratio of the change (not the absolute number of seconds). How does this change compare to the computational complexity change for each algorithm comparison?
b) Analysis of the differences in time between algorithms for each array size and how it compares to the algorithms computational complexity. Again, focus on the ratio of the change.
c) Inspect the code for the Exchange sort version 1 and Exchange sort version 2 algorithms. Determine the difference in implementations. Provide analysis on the sorting time difference and how it relates to the implementation.
d) Summarize your findings and provide any comments or analysis on computational complexity with respect to this experiment.
Design and create a variable length Huffman code for the following character set with associated probabilities of occurrence:
A 0.45 B 0.22 C 0.13 D 0.08 E 0.06 F 0.05 G 0.01
Draw a Binary Tree showing the design of the code and create a table showing the characters with their associated Huffman codes. The Huffman codes should be represented by binary numbers.
Calculate the expected (average) length of a character in bits per character using this Huffman code.