Do not understand the median median algorithm for finding the kth element

Question

Below my code is trying to understand the median of the median algorithm (using blocks of size 5). I understand how to get input medians, but I'm not sure how to encode a block to preserve input recursion until I have a median. Then, having received this median, I’m not sure how to use it as a core to throw out useless information to break the input. getMediansArray returns an array of size ceil (input.length / 5) and getMedians simply returns the median of the array (used only for arrays of length <= 5).

 public static int[] findKthElement(int[] input, int k) { int numOfMedians = (int) Math.ceil(input.length/5.0); int[] medians = new int[numOfMedians]; medians = getMediansArray(input, medians) // (1) This only gets the first iteration of medians of the // input. How do I recurse on this until I just have one median? // (2) how should I partition about the pivot once I get it? } public static int[] getMediansArray(int[] input, int[] medians) { int numOfMedians = (int) Math.ceil(input.length/5.0); int[] five = new int[5]; for (int i = 0; i < numOfMedians; i++) { if (i != numOfMedians - 1) { for (int j = 0; j < 5; j++) { five[j] = input[(i*5)+j]; } medians[i] = getMedian(five); } else { int numOfRemainders = input.length % 5; int[] remainder = new int[numOfRemainders]; for (int j = 0; j < numOfRemainders; j++) { remainder[j] = input[(i*5)+j]; } medians[i] = getMedian(five); } } return medians; } public static int getMedian(int[] input) { Arrays.sort(input); if (input.length % 2 == 0) { return (input[input.length/2] + input[input.length/2 - 1]) / 2; } return input[input.length/2]; } 

Answer 1

The median of medians is basically just a quick pick algorithm ( http://en.wikipedia.org/wiki/Quickselect ). Although fast sampling has an average time complexity of O (n), it can slow down to O (n ^ 2) for complex input.

What you do after finding the median of the medians is nothing more than an iteration of the quick pick algorithm. The median of medians has the nice property that it will always be more than 30% of the elements and less than 30% of the elements. This ensures that a quick selection using the median of the medians for the bar will be performed in the worst case of complexity O (n). Refer to: http://en.wikipedia.org/wiki/Median_of_medians

I suggest you start by implementing quick choices. Once you do this, you can use the code that you already have to select the rotation at each step of the quick selection.

Answer 2

If I remember correctly ( updating my memory ) Median of the median chooses the approximate median. I do not understand how it can be used to select the k-th element.