The median of an array is defined to be the value of the "middle" element, if there are an odd number of elements, and otherwise the average of the two middle elements. Thus the median of A = {18, 14, 23, 11, 19} is 18. For simplicity right now, we'll assume the array has an odd number of elements and that the array starts with A[0].

1. Give a simple Θ(n*log(n)) algorithm to determine the median of any array. [Any sorting algorithm with guaranteed Θ(n*log(n)) time will work here, such as mergesort or heapsort. You sort into order and select the value of the middle element. Quicksort does not have guaranteed Θ(n*log(n)) performance and so doesn't satisfy this question, though as we know a randomized version would be a good choice in practice.]

2. Consider an array with 13 elements: {16, 19, 9, 5, 13, 8, 7, 4, 21, 2, 6, 11, 18}. We want to find its median.

   To find the median, we are going to apply your text's partition algorithm to this array and then repeatedly to subarrays of it, more or less as with quicksort. At each stage, however, we focus on only one side of the partition (one side of the pivot) and ignore the other side. Below is an example.

   Each stage (row) below labeled "Partition" is the result of an entire application of Partition, all its steps. After completing the partition, the pivot is colored red.

   Each stage (row) below labeled "Subarray" focuses on one side of the partition and puts parentheses around the numbers on the other side. Once numbers have parentheses around them, they are ignored from then on.

   The middle location of the array is marked with a hat ^. [This part requires no answer.]

   | ^ | 0 1 2 3 4 5 6 7 8 9 10 11 12 -----------|------------------------------------------------------------------ Array | 16 19 9 5 13 8 7 4 21 2 6 11 18 | Partition 1| 16 9 5 13 8 7 4 2 6 11 18 19 21 | Subarray 1 | 16 9 5 13 8 7 4 2 6 11 (18) (19) (21) | Partition 2| 9 5 8 7 4 2 6 11 16 13 (18) (19) (21) | Subarray 2 | 9 5 8 7 4 2 6 (11) (16) (13) (18) (19) (21) | Partition 3| 5 4 2 6 9 8 7 (11) (16) (13) (18) (19) (21) | Subarray 3 | (5) (4) (2) (6) 9 8 7 (11) (16) (13) (18) (19) (21) | Partition 4| (5) (4) (2) (6) 7 8 9 (11) (16) (13) (18) (19) (21) | Subarray 4 | (5) (4) (2) (6) (7) 8 9 (11) (16) (13) (18) (19) (21) | Partition 5| (5) (4) (2) (6) (7) 8 9 (11) (16) (13) (18) (19) (21) |

3. From the table above, is it obvious that we have found the median? What is the value of the median?

4. What determines which side of the partition we keep and which side we ignore above? [In each case we are keeping the portion of the partition that contains the middle index 6.]

5. The algorithm continues repeatedly until the new pivot is located in the middle element. This could occur early on. Give a simple alteration of the order of the numbers in the array above so that the algorithm terminates after the first partition. (Keep the array the same size and mostly the same.) [If we interchange A[2] with A[12] (that is, stick the median value in the pivot position), then the algorithm terminates after one call to partition. This is because the termination condition is for A[6] to equal the pivot.]

6. Give an argument that the algorithm terminates with the correct median value. [As in question 4 above, the algorithm terminates when A[6] is equal to the pivot. At this point all A[i] for i < 6 must be < A[6] and all A[i] for i > 6 must be > A[6]. This is the definition of median. Note that we have the median even though the array will not usually be in sorted order, that is, we haven't (usually) completely sorted the array, but we've still gotten it split at the median.]

7. Write your own program to find the median of an array with an odd number of elements as above. You should base your program on the "minimal" quicksort code found in quicksort. I only want code that will work for this particular instance (array of an odd number of integers), and I don't want you to adapt a median-finding algorithm from some other source. Test your program with the given array, and with the array A = {43,22,51,19,11,67,13,36,32,49,28,15,38}; (the same size). Of course this program should not sort the array and should run in time Θ(n).

   // Median.java: finds median value public class Median { public int median(int[] A, int p, int r, int mid) { printa(A, p, r); int pivot = partition(A, p, r); printa(A, p, r); if (mid == pivot) return A[mid]; else if (mid < pivot) return median(A, p, pivot-1, mid); else return median(A, pivot+1, r, mid); } public int partition(int[] A, int p, int r) { int x = A[r]; int i = p - 1; for (int j = p; j < r; j++) { if (A[j] <= x) { i++; exchange(A,i, j); } } exchange(A, i+1, r); return i + 1; } private void exchange(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; }

   private void printa(int[] A, int p, int r) { int i = 0; while (i < p) printn2(A[i++]); for (i = p; i <= r; i++) printn1(A[i]); i = r+1; while (i <= A.length - 1) printn2(A[i++]); System.out.println(); } void printn1(int i) { if (i < 10) System.out.print(" " + i + " "); else System.out.print(" " + i + " "); } void printn2(int i) { if (i < 10) System.out.print(" (" + i + ")"); else System.out.print(" (" + i + ")"); } public static void main(String[] args) { int[] A = {43,22,51,19,11,67,13,36,32,49,28,15,38}; Median med = new Median(); System.out.println("Median:" + med.median(A,0,A.length-1,(A.length-1)/2)); } }

   0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 -----------|------------------------------------------------------------------ Array | 43 22 51 19 11 67 13 36 32 49 28 15 38 | Partition 1| 22 19 11 13 36 32 28 15 38 49 43 51 67 | Subarray 1 | 22 19 11 13 36 32 28 15 (38) (49) (43) (51) (67) | Partition 2| 11 13 15 19 36 32 28 22 (38) (49) (43) (51) (67) | Subarray 2 | (11) (13) (15) 19 36 32 28 22 (38) (49) (43) (51) (67) | Partition 3| (11) (13) (15) 19 22 32 28 36 (38) (49) (43) (51) (67) | Subarray 3 | (11) (13) (15) (19) (22) 32 28 36 (38) (49) (43) (51) (67) | Partition 4| (11) (13) (15) (19) (22) 32 28 36 (38) (49) (43) (51) (67) | Subarray 4 | (11) (13) (15) (19) (22) 32 28 (36) (38) (49) (43) (51) (67) | Partition 5| (11) (13) (15) (19) (22) 28 32 (36) (38) (49) (43) (51) (67) | Subarray 5 | (11) (13) (15) (19) (22) (28) 32 (36) (38) (49) (43) (51) (67) | Partition 5| (11) (13) (15) (19) (22) (28) 32 (36) (38) (49) (43) (51) (67) | Median: 32

   [Notice that the final line is NOT sorted (not quite). In a larger example the fact that it is not sorted would be more dramatic.]

8. Suppose the array length is anything, either odd or even, and suppose you want to find the value of the ith element in the array, for i = 0, 1, 2, ..., A.length-1. (In the examples above, we were finding the 6th element's value.) Modify your program so that it will find the ith element's value for i in the proper range. Test your modified program with each of the two sets of data and with i = 9. (Again the program should not sort the data.) [In the previous algorithm, you just use the index i as the third parameter in the main call to the function median, instead of calling median with (A.length-1)/2). Inside median, this parameter would still be called mid even though it's no longer necessarily in the middle.]

9. What are you finding when i = 0? What are you finding when i = A.length-1? Would it be interesting to have an Θ(n) algorithm for these two cases? [You would be finding the minimum value of the array in Θ(n) time, which we can do in a simpler fashion. In the other case we would be finding the maximum.]