CS 201: Data Structures

Sorting

Hand in Sorter.java and sorting-report.pdf.

Work alone or with a partner of your choice.

Goals

• Get comfortable with the most well-known O(N^2) sorting algorithms
• Get comfortable with the most well-known O(N*log(N)) sorting algorithms
• Think again about how Big-O analysis and practical observation align

Relevant code

• Sorter.java. Starter code for you.

Getting to know Sorter.java

Play around with Sorter.java to get to know it. Here are a few things you could do to get started. Do not hand in anything from this section.

• Compile Sorter.java and run "java Sorter". Read the usage statement.
• Try sorting 20 integers using Selection Sort. Did it work? How can you tell? How confident are you that it worked, and why? How is the "--verbose" command-line flag relevant?
• Read through the existing methods. What does shuffle do? Which sorting algorithms are implemented and which are not?

Your tasks

For each of the following, add relevant code (if necessary) to your copy of Sorter.java, and write explanations in your sorting-report.pdf.

1. Collect enough timing data to say whether this implementation of Selection Sort is behaving as you expected based on our Big-O analysis of the algorithm.
2. Same thing, but for Merge Sort.
3. For Selection Sort, Insertion Sort, and Merge Sort, identify the line(s) of code you would need to change to make the resulting array go in decreasing order instead of increasing order. Answer this one by showing in your sorting-report.pdf the relevant lines of code for each algorithm, and how they would need to change.
4. Add an implementation of Quicksort to Sorter.java. Test it to make sure you got it right. If you borrowed the code from somewhere, cite your source.

5. Add code to Selection Sort, Insertion Sort, Merge Sort, and Quicksort to count the number of times each algorithm compares two elements of the array being sorted. Collect comparison-count data for a few representative values of N for all three algorithms. Report your observations something like this:

   
   

   N	Selection	Insertion	Merge	Quick
   100	[# of comparisons]	...	...	...
   1000	...	...	...	...
   2000	...	...	...	...
   3000	...	...	...	...
   4000	...	...	...	...

6. Try generating the table from the previous question again. Which numbers stay the same (if any) and which change (if any)? Why?

And of course...

Start early, ask questions, and have fun!