Algorithm of the day -

The Median of Medians Algorithm

Summary

The Median of Medians algorithm is a selection algorithm that finds the k-th smallest element in an unsorted list, it is used for finding the median or any other percentile in a list of numbers

Use Case

The algorithm can be used in a scenario where you have a large list of exam scores and you want to find the median score, this can be useful in statistics and data analysis

Steps

  1. Divide the list into smaller chunks of 5 elements each
  2. Find the median of each chunk
  3. Recursively find the median of the medians
  4. Partition the list around the median of medians
  5. Recursively search for the k-th smallest element in the appropriate partition

Complexity

The time complexity of the Median of Medians algorithm is O(n) and the space complexity is O(1) making it very efficient for large lists

Code Example

import random

def median_of_medians(arr, k):
    if len(arr) <= 5:
        return sorted(arr)[k]
    medians = [sorted(arr[i:i+5])[len(arr[i:i+5])//2] for i in range(0, len(arr), 5)]
    median_of_medians = median_of_medians(medians, len(medians)//2)
    left = [x for x in arr if x < median_of_medians]
    right = [x for x in arr if x > median_of_medians]
    if k < len(left):
        return median_of_medians(left, k)
    elif k >= len(left) + 1:
        return median_of_medians(right, k - len(left) - 1)
    else:
        return median_of_medians

def main():
    arr = [random.randint(1, 100) for _ in range(20)]
    k = 10
    print(median_of_medians(arr, k))
if __name__ == '__main__':
    main()