The median of an array of integers is the value that would belong in the middle position of the array if the array were sorted. For example, consider the following array:

int[] arr = {4, 18, 12, 34, 7, 42, 15, 22, 5}; 

The median of this array is 15, because that value would end up in the middle position if the array were sorted:

int[] arr = {4, 5, 7, 12, 15, 18, 22, 34, 42}; 

If an array has an even number of elements, the median is the average of the elements that would belong in the middle two positions of the array if the array were sorted.

In the file Median.java, implement a program that finds the median of an array of integers by using the partitioning approach taken by quicksort. However, for the sake of efficiency, you should not sort a subarray if it could not contain the median.

In Median.java, we have given you the following:

copies of the swap() and partition() methods from our Sort class. The recursive method that you will write should call the partition() method to process the necessary portions of the array (see below). You should not need to change these methods.

the skeleton of a method named findMedian() that will serve as a wrapper method around your recursive median-finding method, just as the quickSort() method in our Sort class serves as a wrapper around the recursive qSort() method. To implement this wrapper method, all you need to do is add an appropriate initial call to your recursive method. You should not change the header of this method in any way.

a main() method that you should fill with code that tests your median-finding algorithm. We have included sample definitions of odd- and even-length arrays that you can use as you see fit. Make sure that your main() method calls the wrapper method, rather than calling the recursive method directly.

The recursive method that you write will be similar to the recursive qSort() method in our Sort class. However, you will need to modify the algorithm so that it allows you to put the median value or values in the appropriate positions without actually sorting the entire array. You are expected to only sort as much of the array as is necessary to determine the median value, and for full credit you must avoid calling partition() on subarrays that could not possibly contain the median value (see below).

Your recursive method only needs to succeed in getting the median value (or values, in the case of an even array) into the middle position (or positions, in the case of an even array). It does not need to return the median value; it may simply be a void method. Your main() method can then print the median value by looking at the value(s) in the middle position(s) of the array after your algorithm has finished.

Hints:

Your recursive method will be similar to our qSort() method. However, after you call partition(), you need to determine whether to make recursive call(s) to process just the left subarray, just the right subarray, or both subarrays, depending on whether each subarray could contain the median value (or, in the case of an even-length array, at least one of the two median values). When making this decision, remember that after a call to partition(), everything in the left subarray is less than or equal to everything in the right subarray. Given this fact, and given the location(s) where the median value(s) must ultimately end up, you should be able to determine whether you need to make a recursive call on a particular subarray. Tracing through some concrete examples may help you to discover the logic.

(Note: Rather than checking to see whether a given recursive call is needed, it is also possible to defer this checking to the start of the next invocation of the method. In other words, the recursive method could begin by checking to see if the current subarray could contain one or more of the median values, and, if it could not, the method could return without doing anything.)

You should be able to accomplish this task with only 4-10 lines worth of changes/additions to the standard quicksort algorithm. If your modifications to the code in qSort() are substantially longer than this, you are likely on the wrong track.

/* * Median.java */ public class Median { /* * swap - swap the values of the array elements at * position a and position b of the array to which arr refers. * Used by the partition method below. */ private static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } /* partition - helper method for your recursive median-finding method */ private static int partition(int[] arr, int first, int last) { int pivot = arr[(first + last)/2]; int i = first - 1; // index going left to right int j = last + 1; // index going right to left while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i < j) swap(arr, i, j); else return j; // index of last element in the left subarray } } /* * findMedian - "wrapper" method for your recursive median-finding method. * It just makes the initial call to that method, passing it * whatever initial parameters make sense. */ public static void findMedian(int[] arr) { // add an appropriate call to your recursive method } /* * Put the definition of your recursive median-finding method below. */ public static void main(String[] args) { // the median of this array is 15 int[] oddLength = {4, 18, 12, 34, 7, 42, 15, 22, 5}; // the median of this array is the average of 15 and 18 = 16.5 int[] evenLength = {4, 18, 12, 34, 7, 42, 15, 22, 5, 27}; /* Put code to test your method here. */ } }