kth-biggest algorithm

如何在不排序的情況下，找出第k大的值(kth-largest algorithm)


這是前幾天在看八卦板的時候看到有人提到，其中提到了這題目是有O(n)的解法。一時好奇就查了一下，結果發現了以往的認知都是錯的…  所以寫來記錄

先寫一下結論：
1:是有o(n)的解法，但是演算法過於複雜，且常數k 很大，因此除非n很大，而且真的有絕對的必要，還是少使用。

2: 一般用半quicksort, selectsort的方法解此題，雖然複雜度是O(nlogn)，但其實計算過後，worst case是O(n^2)，但average case是O(n)
(後面會寫數學公式)




在開始介紹之前：我想大家大概都想得到最簡單的解法：
1: sort O(nlogn)
2:取出第k值

這是最快、最簡單的方式，只要學過演算法的人通常都可以馬上想到這個方法。

但是這個演算法有兩個的問題：

1.  為什麼一定要排完整個數列呢？在排序的時候，其實很多資料跑一半就已經知道不可能的值，為什麼不能夠移除呢？
2. 這個演算法受限於排序的效能，也就是永遠的最佳解就只能是O(nlogn)。

因此：我以前的作法是類似quicksort的前半段(有人說這叫select sort)

1:取出一個值當作pviot值，查出他屬於第幾大的值，將之放到正確的位置，
然後比他小的放到左邊，比他大的放到右邊

2: 然後k如果是在左邊，則把左半邊繼續進行quicksort，右半邊不用了。
     同理，如果k在右邊，則把左半邊繼續進行quicksort.

直到找到值為止。

這是演算法的變型。其實這就是quick select而已。我想得到的，當然那些強大的數學家、科學家等也都想得到。

但quicksort的問題也很明顯，那就是
如果每次選到的值都是排序的，那 worst case就會很慘。

因此，聰明的數學家用了一個order statistic來避免worst case，並且用很快的方法找出接近中位數的數值，並且用該數字用作pviot值，使quiuck sort的切partition切的非常準確。
(換句話說，就是用尋找中位數的原理找出中位數，接著用中位數當作pivot值，這樣子就會是quicksort的最佳解)


(這邊有一個數學上的計算，有興趣可以看一下參考資料中投影片裡面的證明，大致上是說如果每一次的pivot值都可以讓你去除1/10以上的值，那麼速度將會是theta n(不知道怎麼打出來XD)


相當於quicksort每一次選擇都是選擇最佳的pivot值。
(後來查詢，這也是quicksort避免worstcase的方法，用一些方法，讓他可以盡量的選到最佳的pivot值。


----
okay，這邊用白話文寫一下這個演算法
1:  用快速查找中位數的方法，找出一個中位數(該演算法不會是正確解，但是會是很接近的解)，將中位數定義為pivot
 (2~3為quicksort演算法中的一部份，可以參考quicksort)
2:將pivot值依大小排到他的位置
3:然後將比它大的值放一堆，比它小的值放一堆
4:如果k < pivot的位置 則取Array(1...k-1)  重複1~3的動作
           k> pivot的位置  則取Array(k+1...N) 重複1~3的動作
          k=pivot的位置：直接找到



寫成演算法則是：

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

是一個很好的演算法。但缺點是O(n)的常數k很大，但畢竟比起先排序的方法好很多，

P.S.這個演算法也可以應用在加快quicksort(用在選pivot值)上面。
P.P.S. 這個題目我面試的時候遇過數次，(通常是引導式的叫我回答，不是一定要我找出線性的解答)


參考資料：

http://en.wikipedia.org/wiki/Selection_algorithm

http://en.wikipedia.org/wiki/Order_statistic
http://c3p0demo.googlecode.com/svn/trunk/scalaDemo/script/Order_statistics.ppt


http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on