1 """Copyright (C) 2004 Paul Brossier <piem@altern.org>
2 print aubio.__LICENSE__ for the terms of use
6 Copyright (C) 2004 Paul Brossier <piem@altern.org>
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 original author Tim Peters
25 modified by Paul Brossier <piem@altern.org>
26 inspired from http://www.ics.uci.edu/~eppstein/161/python/peters-selection.py
29 def short_find(a, rank):
33 # Find the rank'th-smallest value in a, in worst-case linear time.
34 def percental(a, rank):
38 return short_find(a, rank)
40 ## Find median of median-of-7's.
41 ##medians = [short_find(a[i : i+7], 4) for i in xrange(0, n-6, 7)]
42 #median = find(medians, (len(medians) + 1) // 2)
44 # modified to Find median
45 median = short_find([a[0], a[-1], a[n//2]], 2)
47 # Partition around the median.
57 a[i], a[j] = a[j], a[i]
62 return percental(a[:i], rank)
64 return percental(a[i:], rank - i)