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
なんとなくきったないけど動いてそげ。