WikiGalaxy
Median of Medians Algorithm
Introduction to Median of Medians
The Median of Medians is an algorithm used to find the approximate median of a list. It is often employed in the selection problem to find the k-th smallest element in an unsorted list, providing a linear time complexity in the worst case.
Algorithm Explanation
The algorithm divides the list into groups of five elements, finds the median of each group, and recursively applies the same process to the list of medians. Eventually, this helps in determining the true median of the original list.
Steps Involved
- Divide the list into groups of five elements.
- Sort each group and find the median.
- Collect the medians into a new list.
- Recursively find the median of this new list.
- Use this median as a pivot to partition the original list.
Complexity Analysis
The Median of Medians algorithm ensures a time complexity of O(n) for the selection problem, making it highly efficient for large datasets.
Applications
This method is particularly useful in scenarios where a quick selection of a k-th smallest element is required, such as in Quickselect and other partition-based algorithms.
import java.util.Arrays;
class MedianOfMedians {
public static int findMedian(int[] arr, int l, int r, int k) {
if (k > 0 && k <= r - l + 1) {
int n = r - l + 1;
int i;
int[] median = new int[(n + 4) / 5];
for (i = 0; i < n / 5; i++)
median[i] = findMedianUtil(Arrays.copyOfRange(arr, l + i * 5, l + i * 5 + 5), 5);
if (i * 5 < n) {
median[i] = findMedianUtil(Arrays.copyOfRange(arr, l + i * 5, l + i * 5 + n % 5), n % 5);
i++;
}
int medOfMed = (i == 1) ? median[i - 1] : findMedian(median, 0, i - 1, i / 2);
int pos = partition(arr, l, r, medOfMed);
if (pos - l == k - 1)
return arr[pos];
if (pos - l > k - 1)
return findMedian(arr, l, pos - 1, k);
return findMedian(arr, pos + 1, r, k - pos + l - 1);
}
return Integer.MAX_VALUE;
}
public static int findMedianUtil(int[] arr, int n) {
Arrays.sort(arr);
return arr[n / 2];
}
public static int partition(int[] arr, int l, int r, int x) {
for (int i = l; i < r; i++) {
if (arr[i] == x) {
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
break;
}
}
int i = l;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
public static void main(String[] args) {
int[] arr = {12, 3, 5, 7, 4, 19, 26};
int n = arr.length, k = 3;
System.out.println("K'th smallest element is " + findMedian(arr, 0, n - 1, k));
}
}
Conclusion
The Median of Medians algorithm is a powerful method for finding order statistics with guaranteed linear time complexity. Its robustness makes it suitable for use in various computational problems.
