ThinkStats (12)

演習 3-4 確認。wikipedia の「選択アルゴリズム」の例としては qsort 的ナニではなくて以下を、な方向で。

function select(a[1..n], k)
     for i from 1 to k
         minIndex = i
         minValue = a[i]
         for j from i+1 to n
             if a[j] < minValue
                 minIndex = j
                 minValue = a[j]
         swap a[i] and a[minIndex]
     return a[k]

wikiepdia の選択アルゴリズム より引用
非線形選択アルゴリズム、とありますね。
ちっさいのを順に数えあげることができれば良いのかな。

def Percentile(scores, percentile_rank):
    n = 0
    for i in scores:
        minValue = i
        minIndex = n
        nn = n+1
        for j in scores[n+1:]
            if j < minValue:
                minIndex = nn
                minValue = j
            nn += 1
        tmp = scores[n]
        scores[n] = scores[minIndex]
        scores[minIndex] = tmp
        if PercentileRank(scores, scores[n]) >= percentile_rank:
            return i
        n += 1

なんとなくきったないけど動いてそげ。