Hey everyone I'm in the process of writing a program that will take a randomly generated generic array, partition it (using a partitioning strategy similar to a quicksort) into 2 subarrays, and following certain guidelines find the median after sorting. Here's the directions to make it clearer:

Ok so here is my code with some comments where I'm having trouble:Quote:

The media of a collection of data is the middle value. One way to find the median is to sort the data and take the value that is at or nearly at the center of the collection. But sorting does more than necessary to find the median. You need to find only the kth smallest element in the collection for an appropriate value of k. To find the median of an item, you would take k as n/2 rounded up.

you can use the partitioning strategy of quicksort to find the kth smallest element in an array. After choosing a pivot and forming the subarrays smaller and larger, you can draw one of the following conclusions:

-if smaller contains k or more elemnts, it must contain the kth smallest element

-if smaller contains k-1 elements, the kth smallest element is the pivot

-if smaller contains fewer than k-1 elements, the kth smallest element is in larger

you can develop a recursive solution to finding the smallest element. the first and last conclusions correspond to the recursive calls. The remaining one is the base case. implement a recursive method that finds the kth smallest element in an unsorted array. Use your method to find the median in the array.

Code :

public class Median { public static <T extends Comparable<? super T>> T getMedian(T[] array, int n, int low, int high) { int i = low; //going to use low and high as indexes that would point to the first element in each sub array, not sure how to get it implemented properly int j = high; T[] smaller = null; T[] larger = null; n = array.length; T pivot =array[n/2]; System.arraycopy(array, 0, smaller, 0, (n/2)-1); //not sure if these work properly, I wasn't able to develop a test program(I HATE GENERICS :mad:) System.arraycopy(array, n/2 , larger, 0, (n/2)); if(smaller[i].compareTo(pivot) < 0) { //how to create a recursive solution here? and also what variable would I put between the brackets, i or another variable? } else if(smaller[i].compareTo(pivot) > 0) { //and here too } else if(smaller[i].compareTo(pivot) == 0) { return pivot; //this is the only one i think that makes sense, but do I return pivot or some other value that i set equivalent to pivot? } } }

I know it probably looks like a mess, but I think I'm on the right track in terms of my thought process. It's just ironing out these kinks. I also have a provided testclass called MedianTest that calls this class, uses it to find the median, and compares its performance to the quicksort. My class should be more efficient, probably closer to O(n) instead of O(logn).

Somebody help!