Mystery Sort

Supporting files:

MysterySort.jar
Generate.java

Objectives:

• to gain a better understanding of different sorting algorithms.
• to understand how the nature of input can affect the performance of an algorithm.

Distributed with this assignment is a program named Mystery Sort. After select a file of numbers, you tell it to sort the numbers using one of five algorithms labeled A through E. Mystery Sort measures how long it takes to sort the numbers according to that algorithm. For this assignment, you should determine what algorithm each letter represents and submit a written report describing your analysis. The algorithms are (though probably not in this order):

insertion sort

merge sort

quick sort with random pivot

quick sort with the pivot being the center number in the array

selection sort

The Generate.java program distributed with this assignment is useful for generating sequences of numbers for Mystery Sort to sort. After prompting the user for a file and a length n, the program creates a file with the numbers 0 through n-1 listed in random order. These randomly ordered files are useful; but you will also want to create different orderings to distinguish different algorithms. You can do this by modifying the the createArray method in Generate.java.

One possible pitfall is to judge an algorithm's Big-O performance based on a single value of n. Such an analysis is not valid. To estimate a Big-O bound for an algorithm, you need to measure performance for several values of n and compare the results. For example: To establish that an algorithm takes O(n) time, you would show that doubling n leads to roughly doubling the amount of time the program takes.

In the paper you submit as your solution, you should describe the tests that lead to your final conclusion, the results of those tests (including the raw measurements), your conclusion (i.e., the specific mapping from letters to algorithms), and the rationale behind your conclusion. Do not describe tests that turn out to be unimportant to your conclusions.

You will not submit any code for this assignment.

Your paper will be evaluated based on the correctness of your conclusions, the soundness of your reasoning, and the quality of your writing. The quality of your writing includes issues such as grammar, spelling, clarity of presentation, and ability to engage a reader (i.e., don't be too boring!). Your paper should not exceed two pages, and indeed a two-page paper is likely to be too long.