i th order statistic in Python

Question

Given a list of n comparable elements (say numbers or string), the optimal algorithm to find the ith ordered element takes O(n) time.

Does Python implement natively O(n) time order statistics for lists, dicts, sets, ...?

Answer 1

If i << n you can give a look at http://docs.python.org/library/heapq.html#heapq.nlargest and http://docs.python.org/library/heapq.html#heapq.nsmallest (the don't solve your problem, but are faster than sorting and taking the i-th element).

Answer 2

None of Python's mentioned data structures implements natively the ith order statistic algorithm.

In fact, it might not make much sense for dictionaries and sets, given the fact that both make no assumptions about the ordering of its elements. For lists, it shouldn't be hard to implement the selection algorithm, which provides O(n) running time.

Answer 3

This is not a native solution, but you can use NumPy's partition to find the k-th order statistic of a list in O(n) time.

import numpy as np
x = [2, 4, 0, 3, 1]
k = 2
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k])

EDIT: this assumes zero-indexing, i.e. the "zeroth order statistic" above is 0.