You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2026/04/17 12:01:18 UTC
(commons-numbers) 03/04: Add Selection to user guide
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit a9a7a85c2f53406ff1c5ef29b422c6c41092e237
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Fri Apr 17 12:36:18 2026 +0100
Add Selection to user guide
---
.../apache/commons/numbers/arrays/Selection.java | 19 ++++++++--
.../commons/numbers/arrays/UserGuideTest.java | 12 ++++++
src/site/apt/userguide/index.apt | 44 ++++++++++++++++++++++
3 files changed, 72 insertions(+), 3 deletions(-)
diff --git a/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/Selection.java b/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/Selection.java
index 767928a6..45636ab0 100644
--- a/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/Selection.java
+++ b/commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/Selection.java
@@ -34,16 +34,29 @@ package org.apache.commons.numbers.arrays;
* data [0, 1, 2, 1, 2, 5, 2, 3, 3, 6, 7, 7, 7, 7]
*
*
- * k=4 : [0, 1, 2, 1], [2], [5, 2, 3, 3, 6, 7, 7, 7, 7]
- * k=4,8 : [0, 1, 2, 1], [2], [3, 3, 2], [5], [6, 7, 7, 7, 7]
+ * k=4 : [0, 2, 1, 1], [2], [6, 3, 2, 3, 5, 7, 7, 7, 7]
+ * k=4,8 : [0, 1, 2, 1], [2], [3, 3, 2], [5], [7, 7, 6, 7, 7]
* </pre>
*
- * <p>This implementation can select on multiple indices and will handle duplicate and
+ * <p>Notes:
+ *
+ * <ul>
+ * <li>The algorithm does not require that all data with a value equal to the target index
+ * are ordered consecutively in a range containing the target index.
+ * <li>The algorithm may reorder any part of the array above and below the target indices.
+ * <li>Correct usage for multiple target indices should not call multiple times with each
+ * index but instead call selection only once with all indices. Use of consecutive calls
+ * can reorder previously selected indices.
+ * </ul>
+ *
+ * <p>Selection on multiple indices will handle duplicate and
* unordered indices. The method detects ordered indices (with or without duplicates) and
* uses this during processing. Passing ordered indices is recommended if the order is already
* known; for example using uniform spacing through the array data, or to select the top and
* bottom {@code n} values from the data.
*
+ * <p>Implementation details
+ *
* <p>A quickselect adaptive method is used for single indices. This uses analysis of the
* partition sizes after each division to update the algorithm mode. If the partition
* containing the target does not sufficiently reduce in size then the algorithm is
diff --git a/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/UserGuideTest.java b/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/UserGuideTest.java
index 64c20f19..e19d897e 100644
--- a/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/UserGuideTest.java
+++ b/commons-numbers-arrays/src/test/java/org/apache/commons/numbers/arrays/UserGuideTest.java
@@ -56,4 +56,16 @@ class UserGuideTest {
Assertions.assertArrayEquals(new int[] {1, 0}, c.toMulti(50));
Assertions.assertArrayEquals(new int[] {99, 49}, c.toMulti(4999));
}
+
+ @Test
+ void testSelection1() {
+ int[] data = {0, 1, 2, 1, 2, 5, 2, 3, 3, 6, 7, 7, 7, 7};
+
+ Selection.select(data, 4);
+ Assertions.assertEquals(2, data[4]);
+
+ Selection.select(data, new int[] {4, 8});
+ Assertions.assertEquals(2, data[4]);
+ Assertions.assertEquals(5, data[8]);
+ }
}
diff --git a/src/site/apt/userguide/index.apt b/src/site/apt/userguide/index.apt
index 720eb605..b7738418 100644
--- a/src/site/apt/userguide/index.apt
+++ b/src/site/apt/userguide/index.apt
@@ -208,6 +208,50 @@ c.toMulti(50) // [ 1, 0]
c.toMulti(4999) // [99, 49]
+------------------------------------------+
+ The <<<Selection>>> class provides partial sorting of an array. Selection arranges elements
+ such that indices <<<k>>> correspond to their correctly sorted value in the equivalent fully
+ sorted array. Selection is the same as performing a sort and stopping early when all the desired
+ positions are correctly ordered. In most cases of unordered data, selection will perform faster
+ than a full sort when only some indices from a sorted array are required.
+
+ The following example shows how partial ordering of the elements occurs for selection
+ of indices <<<4>>> or <<<[4, 8]>>> from an array:
+
++------------------------------------------+
+data [0, 1, 2, 1, 2, 5, 2, 3, 3, 6, 7, 7, 7, 7]
+
+k=4 : [0, 2, 1, 1], [2], [6, 3, 2, 3, 5, 7, 7, 7, 7]
+k=4,8 : [0, 1, 2, 1], [2], [3, 3, 2], [5], [7, 7, 6, 7, 7]
++------------------------------------------+
+
+ Note:
+
+ * The algorithm does not require that all data with a value equal to
+ the target index are ordered consecutively in a range containing the target index.
+
+ * The algorithm may reorder any part of the array above and below the target indices.
+
+ * Correct usage for multiple target indices should <<not>> call multiple times with each
+ index but instead call selection only once with all indices. Use of consecutive
+ calls can reorder previously selected indices.
+
+ * Calls with multiple indices are more efficient if the indices are ordered
+ but the method will accept unordered and duplicate indices.
+
+ The equivalent in code is:
+
++------------------------------------------+
+int[] data = {0, 1, 2, 1, 2, 5, 2, 3, 3, 6, 7, 7, 7, 7};
+
+Selection.select(data, 4); // data[4] == 2
+Selection.select(data, new int[] {4, 8}); // data[4] == 2, data[8] == 5
++------------------------------------------+
+
+ Selection is performed in-place and operates on <<<int>>>, <<<long>>> or <<<double>>>
+ arrays. Selection is used in
+ {{{https://commons.apache.org/proper/commons-statistics/}commons-statistics}} to compute
+ the median and quantiles of numeric array data.
+
Combinatorics
The {{{../commons-numbers-combinatorics/index.html}commons-numbers-combinatorics}} module