Description
Goal
In this lab you will build on Quick Sort to write an efficient algorithm for computing order statistics (e.g., median) without sorting the array.
Resources
-
Chapter 8: An Introduction to Sorting
-
Chapter 9: Faster Sorting Methods
Java Files
-
CheckKth.java
-
SortArray.java
The basic and advanced sorts have been implemented in the SortArray class. The class CheckKth will generate some arrays, call the kthItem method, and checks that its output is correct.
Step 1. In SortArray look at the existing code for kthItem(). The private recursive method needs to be completed.
Step 2. Refer to the algorithm from the pre-lab presentation and complete the kthItem() method.
Checkpoint: Run CheckKth with an array size of 10. If it passes, run it again with an array size of 1000. If it fails, debug and retest.
Post-Lab Follow-Up
Implement an iterative version of kthItem. Use CheckKth to verify that the new code works correctly.
Adapted from Dr. Hoot’s Lab Manual for Data Structures and Abstractions with Java ™
