-=-=-=-=- needs review -=-=-=-=-=-
Homework 8: Sorting
In this homework, you’ll implement three of the sorting algorithms from lecture: heapsort, mergesort, and quicksort. Each one sorts an int[] into ascending order.
Reminder that you must follow the style guide, and that you can check style yourself in IntelliJ as many times as you want.
Setup
Follow the Assignment Workflow Guide to get started with this assignment. This starter code is in the hw08 folder.
The skeleton has three files, one per sort: HeapSort.java, MergeSort.java, and QuickSort.java. Each file has TODO comments marking what you need to write. The provided helper methods and method signatures should not be changed.
You may not use java.util.Arrays, java.util.Collections, PriorityQueue, TreeMap, TreeSet, or streams. System.arraycopy is fine.
Task 1: Heapsort
Implement heapsort in HeapSort.java by filling in sort and the suggested helper heapify.
Heapsort works in two phases:
- Turn the array into a max-heap using
heapify. Bubble down every element, starting from the end of the array and working toward the root. - Repeatedly swap the root (the largest remaining element) with the last element of the heap, then bubble down the new root within the unsorted part of the array.
This is an in-place sort: sort returns nothing and should not create any additional arrays.
A few things to note about the skeleton:
- The heap is rooted at index 0, not index 1 like in lecture.
getLeftChildandgetRightChildare provided and already account for this. - We’ve provided
bubbleDown(arr, i, limit), which bubbles down the element at indexibut treats indices at or pastlimitas not part of the heap. This lets you shrink the heap as the sorted portion grows. Read it carefully before you use it.
Task 2: Mergesort
Implement mergesort in MergeSort.java by filling in sort and the suggested helper merge.
Mergesort works as follows:
- Split the array in half.
- Recursively mergesort each half.
- Merge the two sorted halves into one sorted array.
sort is non-destructive: it returns a new sorted array, and the original arr must not be modified. Even for an array of length 0 or 1, return a new array rather than arr itself.
Task 3: Quicksort
Implement quicksort in QuickSort.java by filling in quickSort and the suggested helper partition.
Quicksort works as follows:
- Select a pivot and partition the array in place around it.
- Recursively quicksort the “less than” section and the “greater than” section.
Use the 3-scan partitioning scheme from lecture, always picking the first item in the range as the pivot. After partitioning, the range [start, end) should look like
[ items less than pivot | items equal to pivot | items greater than pivot ]
and partition should return a length-2 array holding the index one past the end of the “less than” section and the index where the “greater than” section starts. Your recursive calls should skip the “equal to” section entirely.
sort is destructive: it sorts arr in place and returns that same array.
Testing
TestSorts.java in the tests folder has one basic test per sort. These are deliberately minimal. Add your own tests with duplicates, empty arrays, single-element arrays, and already-sorted input. The autograder tests all of these.
Submission
Graded files that you need to modify:
HeapSort.javaMergeSort.javaQuickSort.java
You must follow the style guide for all three files. You can check style yourself in IntelliJ as many times as you want.
Follow the Assignment Workflow Guide to submit. You can submit as many times as you want.
-=-=-=-=- needs review -=-=-=-=-=-