UPDATED (REALLY for the last time!) on Friday, 27 April 2018
Part 1. Implement classic sorting algorithms.
- Read and become familiar with the source code posted at Sorts of Sorters.
- Note the exercises defined by comments in the source code. (See next item.)
- Do exercises 1 (a-c), 2 (a-c), 3, and 4.
Part 2. Answer the following questions.
- Henceforth known as Matt Van Winkle sort in honor of the recently awakened Matt Nearman’s keen insight, a technique employed by what was formerly known as Cocktail shaker sort can be used to turn BestBubbleSorter into BestestBubbleSorter. Provide an example of a sequence of strings to be sorted that could be used to demonstrate how Matt Van Winkle sort is better than “plain Jane bubble sort.” Explain what is special about the sequence and why it is well suited to demonstrating the time efficiency of Matt Van Winkle sort.
- What is selection sort? How is it similar to or different from insertion sort?
- A permutation of a finite set is an arrangement of its elements into a sequence. Use (your versions of) the sorters BestBubbleSorter, InsertionSorter, MergeSorter, QuickSorter, and CollectionsSorter to sort all distinct permutations of all subsets of the set { a, b, c, d, e, f, g, h, i }. (HINT: USE a program!) Observe how the average execution time, average comparison count, and (where applicable) average exchange count metrics vary as a function of set size across sorting algorithms by creating charts with the set size on the x-axis, units for one of the metrics on the y-axis, and the values for that metric for each sorter shown on the chart. (Create 3 charts.)
- Create a chart that shows how the number of permutations of a set varies with set size as the set ranges from zero to 10 elements.
- What are the running time orders of growth for bubble sort, insertion sort, merge sort, and quick sort? Choose the best description from among the descriptions listed on page 505 of your textbook: constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential.
Grades, Due Date, and Submitting Your Work
You will receive two scores for this assignment:
- One score will be based on whether your program works correctly or not.
- The other score will be based on your coding style and your answers to the questions.
You may be penalized for not following instructions.
- Email the source code for your entire program as inline text or as an attachment in plain text format to jspurgeon@vcstudent.org by 11:59 pm on Saturday, 5 May 2018. The subject of your email should be Programming Assignment 14.
- Submit hard copies of: only the code you wrote; the output your program produces given the ten command-line arguments: c a b d d a b d a d; and your answers to the questions listed above.
