# Algorithm Chapter 9 - Medians and Order Statistics

## Terminology

* 第 $k$ 順序統計量 ($k$-th order statistic): 在一個大小為 $n$ 的集合中第 $k$ 小的元素
* 最小值 (minimum)： 第一順序統計量
* 最大值 (maximum)： 第 $n$ 順序統計量
* 中位數 (median)： 整個集合當中在正中央的位置的元素
* 如果 $n$ 是奇數，則中位數只有一個， $k = \frac{n + 1}{2}$
* 如果 $n$ 是偶數，則中位數有兩個，分別為 $k = \frac{n}{2}$ 和 $k = \frac{n}{2} + 1$
* **在排序或是選擇問題中，我們所說的「中位數」是指比較小的那個**
* 在統計學中，中位數指的是中間兩個數加起來的平均

## The Selection Problem

* `item selection(set A, index i)`
* Input: 集合 $A$ （由 $n$ 個相異元素組成）， 以及整數 $i$ （$1 \leq i \leq n$）
* Output: $A$ 當中的某個元素 $x$， 其值正好大於 $i - 1$ 個 $A$ 當中的其它元素，即第 $i$ 小的元素

### Comparison-based Selection

* 可以在 $O(nlgn)$ 的時間內解決
* 將 $n$ 個元素排序，並取出排序好的陣列當中的第 $i$ 個
* 由於排序演算法的時間複雜度上限在 $O(nlgn)$， 所以選擇問題的上限也在 $O(nlgn)$
* 只找最大值或最小值，可以在 $O(n)$ 時間內解決
* 將第一個元素設定為最大 / 最小值
* 往後一個一個看，如果比目前的極值更大 / 更小，則更新極值
* 完成 $n - 1$ 次比較後即可獲得最大 / 最小值
* 時間複雜度為 $T(n) = n - 1$， 屬於 $O(n)$ 時間

    function minimum(A, n) {
        let min = A[0];
        for(let i = 1; i < n; ++i) {
            if(min > A[i]) min = A[i];
        }
        return min;
    }
    // To find maximum: change > to <

* 同時找最大值和最小值，也可以在 $O(n)$ 時間內達成
* 簡單版： 執行上面的程式兩次， $T(n) = 2n + 2$
* 進階版： 可以在 $T(n) = 3 \times \lfloor \frac{n}{2} \rfloor$ 之內找到
* 若 $n$ 為偶數，比較前兩個元素，將最大值設為較大者，最小值設為較小者
* 若 $n$ 為奇數，最大值和最小值設為第一個元素
* 往後每兩個元素一數，互相比較取得較大者和較小者
* 比較最大值和較大者，並取其中較大的值為最大值
* 比較最小值和較小者，並取其中較小的值為最小值
* 比完所有的元素後，即同時取得最大值和最小值
* 每兩個元素為一組，共 $\lfloor \frac{n}{2} \rfloor$ 組，每一組只需要比較三次，時間複雜度大約為 $T(n) = 3 \times \lfloor \frac{n}{2} \rfloor$

        function maxAndMin(A, n) {
            let max, min;
            if(n % 2 == 0) {
                max = A[0] > A[1] ? A[0] : A[1];
                min = A[0] === max ? A[1] : A[0];
                for(let i = 2; i < n; i += 2) {
                    let bigger = A[i] > A[i + 1] ? A[i] : A[i + 1];
                    let smaller = A[i] === bigger ? A[i + 1] : A[i];
                    max = bigger > max ? bigger : max;
                    min = smaller < min ? smaller : min;
                }
            }
            else {
                max = A[0];
                min = A[0];
                for(let i = 1; i < n; i += 2) {
                    let bigger = A[i] > A[i + 1] ? A[i] : A[i + 1];
                    let smaller = A[i] === bigger ? A[i + 1] : A[i];
                    max = bigger > max ? bigger : max;
                    min = smaller < min ? smaller : min;
                }
            }
            return {max, min};
        }

### Randomized Selection

* 使用隨機搜尋法，可以以平均時間複雜度的期望值在 $O(n)$ 內的時間找到任意第 $i$ 小的元素
* 利用隨機快速排序法當中的 `RANDOMIZED-PARTITION` 函數取得隨機的 pivot 值，並且把 input 的陣列分成比 pivot 大和比 pivot 小的兩邊
* 若隨機回傳的 pivot 值 index 已經等於 $i$ 了，則完成搜尋
* 若隨機回傳的 pivot 值 index 小於 $i$， 則遞迴往左半邊的陣列搜尋第 $i$ 小的值
* 若隨機回傳的 pivot 值 index 大於 $i$， 則遞迴往右半邊的陣列搜尋第 $i - k$ 小的值（因為已經確定有 $k$ 個值比 $i$ 小，所以在右邊的陣列當中的第 $i - k$ 小的值就是完整陣列中的第 $i$ 小的值）
* 遞迴直到 pivot 為第 $i$ 小的數字或是 subarray 的大小為 1
* 最差的時間複雜度可高達 $O(n^2)$ （理由同快速排序法），但平均時間複雜度的期望值落在 $O(n)$ 當中，算是很迅速的搜尋演算法

    // p = first index in subarray, r = last index in subarray
    function randomized_select(A, p, r, i) {
        if(p === r) {
            return A[p];
        }

        let q = randomized_partition(A, p, r); // pivot index in array A
        let k = q - p + 1; // pivot index in this subarray

        if(i === k) {
            return A[q];
        }
        else if (i < k) {
            return randomized_select(A, p, q - 1, i);
        }
        else {
            return randomized_select(A, q + 1, r, i - k);
        }
    }
    
    function partition(A, p, r) {
        let random = Math.floor(Math.random() * r + 1);
        swap(A, random, r);
        let pivot = A[r];
        let q = p;
    
        for (let i = p; i < r; ++i) {
            if (A[i] <= pivot) {
                swap(A, q, i);
                q++;
            }
        }
        swap(A, r, q);
        return q;
    }

* 時間複雜度分析： 不知道在工三小（。

### Median of Medians

* 使用 Median of Medians 搜尋法，可以在最差時間複雜度為 $O(n)$ 的情況下找到任意第 $i$ 小的數字
* 將 input 的陣列五個五個一數，共可分成 $\lceil \frac{n}{5} \rceil$ 組（最後一組可能不滿五個）
* 用任意一種排序演算法（通常用泡沫排序或插入排序，因為比較好寫）將五個數字排序，並且挑出當中的中位數。因為每一組都只有五個數字，所以每一組要挑出中位數所花的時間是 $O(1)$
* 總共會挑出 $\lceil \frac{n}{5} \rceil$ 個中位數，遞迴進行上面的步驟直到挑出這 $\lceil \frac{n}{5} \rceil$ 個中位數的中位數
* 呼叫快速排序法當中的 `PARTITION` 函數，並且以這個中位數們的中位數為 pivot， 將 input 陣列分成兩邊
* 若 pivot 值 index 已經等於 $i$ 了，則完成搜尋
* 若 pivot 值 index 小於 $i$， 則遞迴往左半邊的陣列進行搜尋
* 若 pivot 值 index 大於 $i$， 則遞迴往右半邊的陣列進行搜尋
* 遞迴直到找到第 $i$ 小的元素或是 subarray 的長度為 1

    function medianOfMedians(A, left, right, i) {
        while(true) {
            if(left === right) {
                return A[left];
            }

            let pivotIndex = pivot(A, left, right);
            pivotIndex = partition(A, left, right, pivotIndex);
            if(i === pivotIndex) {
                return A[pivotIndex];
            }
            else if(i < pivotIndex) {
                right = pivotIndex - 1;
            }
            else {
                left = pivotIndex + 1;
            }
        }
    }
    
    function pivot(A, left, right) {
        if(right - left < 5) {
            return insertion_sort(A, left, right);
        }

        for(let i = left; i <= right; i += 5) {
            let subRight = i + 4;
            if(subRight > right) {
                subRight = right;
            }

            let median5 = insertion_sort(A, i, subRight);
            swap(A[median5], A[left + Math.floor((i - left) / 5)]);
        }

        return medianOfMedians(A,
                               left,
                               left + Math.floor((right - left) / 5),
                               left + Math.floor((right - left) / 10));
    }
    
    function partition(A, left, right, pivotIndex) {
        let pivotValue = A[pivotIndex];
        swap(A[pivotIndex], A[right]);

        let storeIndex = left;
        for(let i = left; i < right; ++i) {
            if(A[i] < pivotValue) {
                swap(A[storeIndex], A[i]);
                storeIndex++;
            }
        }
        swap(A[storeIndex], A[right]);
        return storeIndex;
    }
    
    function insertion_sort(A, left, right) {
        let i, j, tmp;
        for(i = left + 1; i <= right; ++i){
            let tmp = A[i];
            for(j = i; j > left && A[j - 1] > tmp; j--) {
                A[j] = A[j - 1];
            }
            A[j] = tmp;
        }
        return left + Math.floor((right - left) / 2);
    }

* 時間複雜度證明：
* 將 input 的陣列五個五個一數： $O(n)$
* 將五個一組的數字排序，並且挑出當中的中位數：$O(1) \times \lceil \frac{n}{5} \rceil = O(n)$
* 遞迴進行直到挑出這 $\lceil \frac{n}{5} \rceil$ 個中位數的中位數： $T(\lceil \frac{n}{5} \rceil)$
* 呼叫快速排序法當中的 `PARTITION` 函數將 input 陣列分成兩邊： $O(n)$
* 遞迴直到找到第 $i$ 小的元素： $T(7 \times \frac{n}{10} + 6)$
* 在第 2 步排序完的結果當中，每一組都至少有兩個元素是小於 pivot 的
* 在第 4 步 partition 完之後，每一個在 pivot 組之前的組，都貢獻了三個比 pivot 小的數字（同理，在 pivot 之後的組都貢獻了三個比 pivot 大的），除了不滿五個元素的組和 pivot 組自己
* 不考慮最後那兩組的話，總共至少會有 $3 \times ( \lceil \frac{1}{2} \times \lceil \frac{n}{5} \rceil \rceil - 2) \geq 3 \times \frac{n}{10} - 6$ 的數字比 pivot 小 / 大
* 換句話說，當我們遞迴呼叫 `medianOfMedians` 的時候，頂多只會處理 $n - (3 \times \frac{n}{10} - 6) = 7 \times \frac{n}{10} + 6$ 個數字而已，所以最後一步的複雜度是 $T(7 \times \frac{n}{10} + 6)$
* 寫出遞迴式 $$T(n) = \begin{equation} \begin{cases} O(1) \text{, if } n < 140\\ T(\lceil \frac{n}{5} \rceil) + T(7 \times \frac{n}{10} + 6) + O(n) \text{, if } n \geq 140 \end{cases} \end{equation} $$
* （然後就看不懂ㄌ（幹
* 總之最後， $T(n) = O(n)$， 所以這是線性的搜尋演算法

## Note

* [General 的排序演算法，因為其決策樹的長相，決定了任意的排序演算法都至少得花 $\Omega(nlog_2n)$ 的時間才能完成排序](http://www.quretec.com/u/vilo/edu/2003-04/ATABI_2004k/BigOh/sort_lower.html)
* 線性時間的排序演算法對其 input 的定義域有一定要求，不能排序所有的實數
* 線性時間的搜尋演算法不倚靠排序，所以才能逃脫 $\Omega(nlog_2n)$ 的限制
* 且線性時間的搜尋演算法對 input 的定義域沒有限制，可以對任意的 input 序列做搜尋