Download code

Jump to: navigation, search

Back to Nth_element_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

qnth.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Nth_element_(Python)?oldid=9341
14 
15 def qnth(sample, n):
16     pivot = sample[0]
17     below = [s for s in sample if s < pivot]
18     above = [s for s in sample if s > pivot]
19     i, j = len(below), len(sample)-len(above)
20 
21     if n < i:      return qnth(below, n)
22     elif n >= j:   return qnth(above, n-j)
23     else:          return pivot
24 
25 if __name__ == "__main__":
26     import random
27     n, mid = 64, 32
28     sample = [random.random() for _ in range(n)]
29     partial = qnth(sample, mid)
30     sample.sort(); sorted = sample[mid]
31     print partial, sorted, partial == sorted


hijacker
hijacker
hijacker
hijacker