Libraryless. Click here for Pure Java version (10698L/59K).
1 | // defaults to median when idx isn't given |
2 | static <A> A ithSmallest(L<A> l, int idx default l(l)/2) {
|
3 | int n = l(l); |
4 | if (n <= 80) |
5 | ret get(sorted(l), idx); |
6 | int cols = (n+4)/5; |
7 | new L<A> medians; |
8 | for (int i = 0; i < cols; i++) |
9 | medians.add(ithSmallest(subList(l, i*5, 5))); |
10 | |
11 | // median of medians |
12 | A mom = ithSmallest(medians); |
13 | |
14 | L<A> setA = filter(l, a -> lessThan(a, mom)); |
15 | L<A> setB = filter(l, a -> greaterThan(a, mom)); |
16 | |
17 | int nA = l(setA); |
18 | if (idx < nA) |
19 | ret ithSmallest(setA, idx); |
20 | if (idx == nA) |
21 | ret mom; |
22 | ret ithSmallest(setB, idx-nA-1); |
23 | } |
download show line numbers debug dex old transpilations
Travelled to 1 computer(s): mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1071798 |
| Snippet name: | ithSmallest - O(n) ith-smallest element selection [dev.] |
| Eternal ID of this version: | #1071798/6 |
| Text MD5: | 18f8f70d0348fa83a590fc6133d06777 |
| Transpilation MD5: | 706e4d8d0cdc4784718ec7dc67ebb6fa |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2026-09-05 15:58:46 |
| Source code size: | 608 bytes / 23 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 34 / 59 |
| Version history: | 5 change(s) |
| Referenced in: | [show references] |