# Selection 演算法
- [215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)
- 以 median of median 當作 pivot

    // return the kth smallest number in data
    int selection(vector<int> data, int k){
        int n = data.size();
        if(n<=10){
            sort(data.begin(),data.end());
            return data[k-1];
        }
        vector<int> median;
        for(int i=0;i+5<=n;i+=5){
            sort(data.begin()+i, data.begin()+i+5);
            median.push_back(data[i+2]);
        }
        int mom = selection(median, median.size()/2);

        vector<int> a, b;
        for(auto &d : data){
            if(d<mom)       a.push_back(d);
            else if(d>mom)  b.push_back(d);
        }
        int less = a.size(), equal = n - a.size() - b.size();
        if(less >= k)               return selection(a, k);
        else if(less + equal >= k)  return mom;
        else                        return selection(b, k-less-equal);
    }