CSSE 230
Heaps and Two Sorts Programming Assignment

Overview

This assignment is a scaled-down version of the SortingRaces assignment for summer session when there is a week 10 exam.

You will do three things: (1) finish the binary heap implementation if you haven't already done so. (2) You'll use your heap to implement heapsort. (3) You'll implement quicksort.

Details

heaps and heapsort. For the first part of this assignment, you will need your Binary Heap from a previous assignment: heaps.html. Drag and drop BinaryHeap and BinaryHeapTest into your project. If Eclipse gives you an error in BinaryHeapTest, hover your mouse over the first error at the top of that file, and it will give suggestions as to how to fix it (you might need to click the error to see the suggestions). Choose the last option, "Fix Project Setup" and then add JUnit 4 to the build path in the next window. Then run the BinaryHeapMoreTests.java tests to see how your heap does with a more complete set of tests. Debug it if needed.
quicksort. In sort(array) method in the Quicksort class, implement a simple version of quicksort like we did in the lecture. For simplicity, you can hardcode it for type Integer. Try to recall it from the concepts you remember from the lecture, but feel free to refer to the code from the slides or textbook as needed. You may have to modify the given code to handle cases where the pivot repeats. We suggest making a class called Quicksort with a static sort(array) method.
The unit tests give you four different kinds of arrays so you can see how the sort methods handle various conditions.
1. Random order: We have given you tests for this.
2. Random order, but guaranteed to have no duplicates. To create such an array, we created an array such that a[i] = i, and shuffled it using Collections.shuffle that efficiently and throughly shuffles the elements.
3. Almost sorted. Starting with a sorted array of n elements, we perform 0.1*n swaps of pairs of elements in random positions (to "slightly" shuffle it). This will introduce some inversions.
4. Almost sorted, but backwards. Just reversing the array from the previous step.
Your array size should be large enough so that all of your sorts take approximately 25 milliseconds or more. If you go much smaller than that, it will be hard to tell them apart. You can go much larger for most of the sorts.

Frequently Asked Questions

The quicksort code you gave us in class doesn't handle the i and j walking out of bounds. What should I do? Answer: Modify the code to handle that case. It's pretty easy to see if your index has gone further than it needs to.
The quicksort code you gave us in class is giving me a stack overflow error in my recursion. Answer: That code also doesn't consider the case where the pivot element is duplicated - you'll need to handle that too! (When you are sorting arrays with unique elements, this won't be an issue.)
I want to display array ar1 while debugging, but there is no ar1.toString(). Do I need to write my own method to print the array? Answer: No. Instead, call Arrays.toString(ar1)

Deliverables

Commit and push your Git repo, including:

All changed .java files
All newly created .java files

Grading outline