3.5. Quiz

Quiz 3: Sorting Algorithms

Coding

Shell Sort: Hibbard

• Create the ShellSortQuiz class under the sort.comparison package that inherits ShellSort.

• Override the populateSequence() and getSequenceStartIndex() methods such that it performs Shell Sort by using the Hibbard sequence: $2^k - 1 \Rightarrow \{1, 3, 7, 15, \ldots \}$.

• Feel free to use the code in ShellSortKnuth.

Radix Sort: MSD

• Create the RadixSortQuiz class under the sort.distribution package that inherits RadixSort.

• Override the sort() method such that it performs Radix Sort from the most significant digit (MSD) to the least significant digit (LSD).

• Feel free to use the code in sort.distribution.

Testing

• Create the SortQuizTest class under the test sort package.

• Test the correctness of your TernaryHeapQuiz using the testRobustness() method.

• Add more tests for a more thorough assessment if necessary.

Benchmarking

• Compare runtime speeds between ShellSortKnuth and ShellSortQuiz for random, ascending, and descending cases using the testRuntime() method.

• Compare runtime speeds between LSDRadixSort and RadixSortQuiz for random cases.

• Create a PDF file quiz3.pdf and write a report that includes charts and explanations to compare runtime speeds between:

  • ShellSortKnuth and ShellSortQuiz.

  • LSDRadixSort and RadixSortQuiz.

Submission

• Push everything under the sort package to your GitHub repository:

  • Main: src/main/java/edu/emory/cs/sort

  • Test: src/test/java/edu/emory/cs/sort

• Submit quiz3.pdf to Canvas.