k-th largest object in an unsorted list

在一個已知的未排序 list 中尋找第 k 大的物件是經典的 selection 問題。有許多的演算法針對各種變形提出極為優化的解法。底下是我練習 C.A.R. Hoare 的 quickselect ，但我將其改成 not-in-place 的版本。（為何有這篇?因為臨時有一個小時不知道要幹嘛...拿來複習遞迴剛剛好 :-P）

1. #!/usr/bin/env python
2. import random
3.  
4. def kth(L, k):
5.         le = []
6.         eq = []
7.         gt = []
8.         pivot = L[random.randint(0, len(L))]
9.         for e in L:
10.                 if e < pivot:
11.                         le.append(e)
12.                 elif e > pivot:
13.                         gt.append(e)
14.                 else:
15.                         eq.append(e)
16.         if k <= len(gt):
17.                 return kth(gt, k)
18.         elif k <= (len(gt) + len(eq)):
19.                 return pivot
20.         else:
21.                 return kth(le, (k - len(gt) - len(eq)))
22.  
23. print(kth(range(1000), 5))