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
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.
- 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.
- Same thing, but for Merge Sort.
- 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.
- 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.
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 | ... | ... | ... | ... |
- 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!