Algorithms and Data Structures I
Lab 9: Kth Smallest Item
Background
Statisticians often calculate the median of a collection of numbers to inform themselves about the range of data they’re working with. One way to find the median of a data set is to sort the data and find the item in the middle. We can even take it a step further and return the item at index k - 1 to represent the kth smallest item. To get the median, we can set k = data .length / 2 and run our algorithm. This lab will use our knowledge of quicksort to find the kth smallest value in an array.
Exercise
Your job is to implement the kthSmallest method in Lab9.java. The kthSmallest method takes in an unsorted int[] called a and a positive int called k. Your method must return the kth smallest value in the array.
For example, consider an array of ints: int[] numbers = {10, 6, 4, 3, 6, 9, 5}. If we wanted the smallest item in the array, we could call kthSmallest(numbers, 1), which should return 3. If we wanted the second smallest number, we could call kthSmallest(numbers, 2), which should return 4.
To efficiently find the kth smallest item in an array, we can use the partition method from Quicksort. After choosing a pivot and partitioning the array into two subarrays (Smaller and Larger), the following points are true:
- If the smaller partition contains exactly k - 1 entries, the kth smallest item is the pivot value (Hint: this is the base case)
- If the smaller partition contains k or more entries, it must contain the kth smallest entry.
- If the smaller partition contains fewer than k - 1 entries, the kth smallest entry is in the larger partition.
There are many ways to correctly implement this program, but few ways to do it efficiently. The autograder will time your program and will reward more points the faster the program can run. In order to receive full credit, your program must utilize an algorithm that is faster than the naive approach.
Deliverables
You are responsible for submitting Lab9.java with an implemented kthSmallest method.
Grading
Your program will be autograded based on this rubric:
|
Correctly identify the kth smallest item in an array of 4 integers
|
1.0
|
|
Correctly identify the kth smallest item in an array of 100 integers
|
0.25
|
|
Correctly identify the kth smallest item in an array of 1,000,000 integers within 1,000ms
|
0.25
|
|
Correctly identify the kth smallest item in an array of 1,000,000 integers within 500ms
|
0.25
|
|
Correctly identify the kth smallest item in an array of 1,000,000 integers within 300ms
|
0.25
|
Note: If the autograder fails to complete all 5 test cases within 10 minutes, you will receive a 0/2. If all else fails, sort the array using a sorting algorithm from class and then find the kth smallest item.
Additionally, your computer might run faster than the autograder. For example, my efficient submission was able to sort in < 50ms locally but took over 200ms when submitted to gradescope. Check your submission with gradescope early to make sure you aren’t going to lose points!
Hint: Having trouble implementing the algorithm? Take a look at Sorting2.java on Canvas!