---
title: 'Median of Medians'
disqus: hackmd
---

# **Median of Medians**

###### tags: `algo` `python`

Question
---

==對於一個未排序，長度為 n 的數列，能否在 $O(n)$ 的時間複雜度內找到該數列的中位數?==

Method
---

- 想要找到一個數列的中位數，最簡單的方法就是排序數列，然後取出第 $\dfrac{n}{2}$ 的 element 就是答案。雖然這個方法可以得到中位數，但卻處理了過多的資訊：當我們只關心中位數時，並不需要對整個數列都排序。

- 為了找到更符合解這個問題的方法，我們將問題擴大成一個更一般性的問題，
==**如何找到這個數列中第 $i$ 小的數**==，而這裡我們用到類似於 QuickSort 的方法，過程如下:
1. 選擇數列中的一個數作為 pivot，將小於 pivot 的數都丟到 pivot 左邊，大於的都丟到 pivot 右邊，形成 $2$ 個子數列。
2. 計算左子數列的長度，假設為$k$。若$i=k+1$，則找到第 $i$ 小的數。
3. 若 $i<k+1$，代表第 $i$ 小的數出現在左子數列，則遞迴左子數列，同樣找第 $i$ 小的數。
4. 若 $i>k+1$，代表第 $i$ 小的數出現在右子數列，則遞迴右子數列，改成找第 $(i-k-1)$ 小的數。

以上的方法是我們稱為 QuickSelection，是一個 divide-and-conquer 的方法，但並不難看出這個方法會和 QuickSort 一樣，在 worst case（pivot 選到最大或最小）的情況下，時間複雜度將會是 $O(n^2)$。

- 為了保證演算法最終在 $O(n)$ 就能找到中位數，我們在上述過程中選擇 pivot 的時候需要一點策略來保證分割出來的兩子數列個數盡量接近以避免 worst case。而 Median of Medians 演算法提供了一個解決辦法。

Median of Medians Algorithm
---

- Median of Medians 決定 pivot 的過程如下:
1. 將數列每 $5$ 個數分成一組，最後不足 $5$ 個的一組數量為 (n Mod $5$)，總共會有 $\lceil \dfrac{n}{5} \rceil$ 組。
2. 每一組在組內進行排序得到中位數。
3. ==將每一組的中位數取出，再遞迴取出這些中位數的中位數直到剩下一個數==。
4. 以3.的結果作為 pivot

- 這樣選擇 pivot 的方法會相較於隨機決定更接近真正的中位數並且將不會掉入 worst case。為了證明，我們要去計算左子數列的個數最多可能為多少（等價於計算右子數列個數），畢竟我們的目的是要找 **第 $i$ 小的數**。
\
首先，==計算左子數列個數相當於計算 *可能* 小於 pivot 的個數有多少==。
\
以下圖為例，整個數列被我們以各組中位數排列後，每一組越上方的數越大，而組跟組之間以中位數排序，越右邊越大。而中間的 $x$ 就是我們這一輪的 pivot。在這些數中，紅色的框框是我們已知一定大於 pivot 的數，而這些數以外的數就是我們 *可能* 小於 pivot 的數。數量總共有:
* (左半邊) 組數的一半 $\dfrac{1}{2}\times \lceil \dfrac{n}{5} \rceil\times$ 每組 $5$ 個數 $\implies \dfrac{5}{2} \lceil \dfrac{n}{5} \rceil$
* (右下角) median 大於 pivot 的各組中都會有 $2$ 個數可能小於pivot，所以加上 $2\times\dfrac{1}{2} \lceil \dfrac{n}{5} \rceil = \lceil \dfrac{n}{5} \rceil$
* 再加上 pivot 本身所在的組中小於 pivot 的 $2$ 個數
\
總共會有:
\
$\implies\dfrac{5}{2} \lceil \dfrac{n}{5} \rceil + \lceil \dfrac{n}{5} \rceil + 2=\dfrac{7}{2} \lceil \dfrac{n}{5} \rceil+2\le\dfrac{7n}{10}+6$

<center>

[Median of medians](https://commons.wikimedia.org/wiki/File:Median_of_medians_time_complexity.png)

</center>

- 因此，每一次我們使用 median of medians 找到 pivot，都能保證最多只會有 70% 左右的數小(大)於 pivot，而不至於落入 worst case。

Time Complixity
---

- 有了保證不至於落入 worst case 後，我們要進一步計算 median of medians 演算法的時間複雜度。
從上述的 [Median of Medians Algorithm 3.步驟](#Median-of-Medians-Algorithm) 中，我們知道在找尋 pivot 的過程是遞迴計算每一組的中位數，直到剩下一個數，而我們在每一回合以 pivot 區分完左右子數列後，也是以同樣的方式遞迴再進行下一次的 pivot 找尋。所以兩者其實是同樣的計算方式。
- 因此，如果我們將 $T(n)$ 看成是找到長度為 $n$ 的數列的中位數所需要的時間，那麼時間複雜度可以寫成：
\
$T(n) \le T(\lceil \dfrac{n}{5} \rceil)+T(\dfrac{7n}{10}+6)+O(n)$
\
其中，不等式右邊第一項為每次分組後從各組中位數中再取中位數，第二項為每次分割後的 worst case 找中位數，最後項 $O(n)$ 為每一次決定完 pivot 後用於比較並分割左右子數列。
根據 [Master Theorem](https://brilliant.org/wiki/master-theorem/) 這個遞迴式的時間複雜度為 $O(n)$。

Code
---
python

import time
import numpy as np

def median_of_medians(arr):
    if arr is None or len(arr) == 0:
        return None
    
    return select_pivot(arr, len(arr)//2)

def select_pivot(arr, k):
    chunks = [arr[i : i+5] for i in range(0, len(arr), 5)]

    sorted_chunks = [sorted(chunk) for chunk in chunks]

    medians = [chunk[len(chunk)//2] for chunk in sorted_chunks]

    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)//2]
    else:
        pivot = select_pivot(len(medians)//2)

    p = partition(arr, pivot)

    if k == p:
        return pivot

    if k < p:
        return select_pivot(arr[0:p], k)
    else:
        return select_pivot(arr[p+1:len(arr)], k-p-1)

def partition(arr, pivot):
    left = 0
    right = len(arr) - 1
    
    i = 0
    while i <= right:
        if arr[i] == pivot:
            i += 1
        elif arr[i] < pivot:
            arr[left], arr[i] = arr[i], arr[left]
            left += 1
            i += 1
        else:
            arr[right], arr[i] = arr[i], arr[right]
            right -= 1
    return left

if __name__ == "__main__":
    print("Input array: ", end='')
    arr = input()
    arr = np.array(list(map(int, arr.split(" "))))

    start = time.perf_counter()
    median = median_of_medians(arr)
    end = time.perf_counter()

    print("The median: " + str(median))
    print("Execution time: " + str(end - start))

參考資料 :
[The Median-of-Medians Algorithm](https://austinrochford.com/posts/2013-10-28-median-of-medians.html)
[Master Theorem](https://brilliant.org/wiki/master-theorem/)
[Python Code](https://gist.github.com/boulethao/a15809963d326a5ad43f255fbffbf9ff)