begin repeat <blockquote>
- TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
- LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE#
- suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
- longlong, ulonglong, half, float, double, longdouble, cfloat, cdouble, clongdouble#
- #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
- npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong, npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat, npy_cdouble, npy_clongdouble#
</blockquote>
iterative median of 3 quickselect with cutoff to median-of-medians-of5 receives stack of already computed pivots in v to minimize the partition size were kth is searched in
area that needs partitioning in [...] kth 0: [8 7 6 5 4 3 2 1 0] -> med3 partitions elements [4, 2, 0]
System Message: ERROR/3 (<string>
, line 7) Unexpected indentation.
<blockquote> 0 1 2 3 4 8 7 5 6 -> pop requested kth -> stack [4, 2]</blockquote>
System Message: WARNING/2 (<string>
, line 8) Block quote ends without a blank line; unexpected unindent.
kth 3: 0 1 2 [3] 4 8 7 5 6 -> stack [4] kth 5: 0 1 2 3 4 [8 7 5 6] -> stack [6] kth 8: 0 1 2 3 4 5 6 [8 7] -> stack []
pivot larger than kth set it as upper bound
kth was already found in a previous iteration -> done
pop from stack
use a faster O(n*kth) algorithm for very small kth e.g. for interpolating percentile
useful to check if NaN present via partition(d, (x, -1))
guarantee three elements
if we aren't making sufficient progress with median of 3 fall back to median-of-median5 pivot for linear worst case med3 for small sizes is required to do unguarded partition
median of 3 pivot strategy, swapping for efficient partition
FIXME: always use pivots to optimize this iterative partition
adapt for the larger partition than med3 pivot
find place to put pivot (in low): previous swapping removes need for bound checks pivot 3-lowest [x x x] 3-highest
move pivot into position
kth pivot stored later
two elements
References IDX, and TYPE.