Repository: TheAlgorithms/Java
Pull request #2860 (2021-12-05 21:00:51)

Feature quick select
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

[Wikipedia Entry](https://en.wikipedia.org/wiki/Median_of_medians)
<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.


Nils-Goldmann: There are two automatic checks that failed: Build and Prettify.

Build uses javac as a compiler in build.yml, while my colleague and I compiled using Maven. I am pretty sure that this is the reason for the failure. How should we proceed on this? We could change build.yml accordingly, if this is an option for you.

Also, Prettify failed and it is not quite obvious to me why. Do you maybe have an idea what the reason could be?
siriak: The prettier is just faulty, nvm
siriak: I've changed builds to maven, the verify command used should run your tests, right?
Nils-Goldmann: > I've changed builds to maven, the verify command used should run your tests, right?

During our work, we used the test command, but verify also seems to work.

Patch:
diff --git a/pom.xml b/pom.xml
index 53e8796e..48f9e1cb 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1,5 +1,7 @@
 <?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
     <modelVersion>4.0.0</modelVersion>
     <groupId>com.thealgorithms</groupId>
     <artifactId>Java</artifactId>
@@ -10,4 +12,37 @@
         <maven.compiler.source>17</maven.compiler.source>
         <maven.compiler.target>17</maven.compiler.target>
     </properties>
+
+    <dependencyManagement>
+        <dependencies>
+            <dependency>
+                <groupId>org.junit</groupId>
+                <artifactId>junit-bom</artifactId>
+                <version>5.8.2</version>
+                <type>pom</type>
+                <scope>import</scope>
+            </dependency>
+        </dependencies>
+    </dependencyManagement>
+
+    <dependencies>
+        <dependency>
+            <groupId>org.junit.jupiter</groupId>
+            <artifactId>junit-jupiter</artifactId>
+            <scope>test</scope>
+        </dependency>
+    </dependencies>
+
+    <build>
+        <plugins>
+            <plugin>
+                <artifactId>maven-compiler-plugin</artifactId>
+                <version>3.8.1</version>
+            </plugin>
+            <plugin>
+                <artifactId>maven-surefire-plugin</artifactId>
+                <version>2.22.2</version>
+            </plugin>
+        </plugins>
+    </build>
 </project>
\ No newline at end of file
diff --git a/src/main/java/com/thealgorithms/searches/QuickSelect.java b/src/main/java/com/thealgorithms/searches/QuickSelect.java
new file mode 100644
index 00000000..fee11cab
--- /dev/null
+++ b/src/main/java/com/thealgorithms/searches/QuickSelect.java
@@ -0,0 +1,140 @@
+package com.thealgorithms.searches;
+
+import java.util.*;
+
+/**
+ * An implementation of the Quickselect algorithm as described
+ * <a href="https://en.wikipedia.org/wiki/Median_of_medians">here</a>.
+ */
+public final class QuickSelect {
+
+    /**
+     * Selects the {@code n}-th largest element of {@code list}, i.e. the element that would
+     * be at index n if the list was sorted.
+     * <p>
+     * Calling this function might change the order of elements in {@code list}.
+     *
+     * @param list the list of elements
+     * @param n    the index
+     * @param <T>  the type of list elements
+     * @return the n-th largest element in the list
+     * @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to
+     *                                   the number of elements in the list
+     * @throws IllegalArgumentException  if the list is empty
+     * @throws NullPointerException      if {@code list} is null
+     */
+    public static <T extends Comparable<T>> T select(List<T> list, int n) {
+        Objects.requireNonNull(list, "The list of elements must not be null.");
+
+        if (list.size() == 0) {
+            String msg = "The list of elements must not be empty.";
+            throw new IllegalArgumentException(msg);
+        }
+
+        if (n < 0) {
+            String msg = "The index must not be negative.";
+            throw new IndexOutOfBoundsException(msg);
+        }
+
+        if (n >= list.size()) {
+            String msg = "The index must be less than the number of elements.";
+            throw new IndexOutOfBoundsException(msg);
+        }
+
+        int index = selectIndex(list, n);
+        return list.get(index);
+    }
+
+    private static <T extends Comparable<T>> int selectIndex(List<T> list, int n) {
+        return selectIndex(list, 0, list.size() - 1, n);
+    }
+
+    private static <T extends Comparable<T>> int selectIndex(
+            List<T> list,
+            int left,
+            int right,
+            int n
+    ) {
+        while (true) {
+            if (left == right)
+                return left;
+            int pivotIndex = pivot(list, left, right);
+            pivotIndex = partition(list, left, right, pivotIndex, n);
+            if (n == pivotIndex) {
+                return n;
+            } else if (n < pivotIndex) {
+                right = pivotIndex - 1;
+            } else {
+                left = pivotIndex + 1;
+            }
+        }
+    }
+
+    private static <T extends Comparable<T>> int partition(
+            List<T> list,
+            int left,
+            int right,
+            int pivotIndex,
+            int n
+    ) {
+        T pivotValue = list.get(pivotIndex);
+        Collections.swap(list, pivotIndex, right);
+        int storeIndex = left;
+
+        for (int i = left; i < right; i++) {
+            if (list.get(i).compareTo(pivotValue) < 0) {
+                Collections.swap(list, storeIndex, i);
+                storeIndex++;
+            }
+        }
+
+        int storeIndexEq = storeIndex;
+
+        for (int i = storeIndex; i < right; i++) {
+            if (list.get(i).compareTo(pivotValue) == 0) {
+                Collections.swap(list, storeIndexEq, i);
+                storeIndexEq++;
+            }
+        }
+
+        Collections.swap(list, right, storeIndexEq);
+
+        return (n < storeIndex)
+                ? storeIndex
+                : Math.min(n, storeIndexEq);
+    }
+
+    private static <T extends Comparable<T>> int pivot(
+            List<T> list,
+            int left,
+            int right
+    ) {
+        if (right - left < 5) {
+            return partition5(list, left, right);
+        }
+
+        for (int i = left; i < right; i += 5) {
+            int subRight = i + 4;
+            if (subRight > right) {
+                subRight = right;
+            }
+            int median5 = partition5(list, i, subRight);
+            int rightIndex = left + (i - left) / 5;
+            Collections.swap(list, median5, rightIndex);
+        }
+
+        int mid = (right - left) / 10 + left + 1;
+        int rightIndex = left + (right - left) / 5;
+        return selectIndex(list, left, rightIndex, mid);
+    }
+
+    private static <T extends Comparable<T>> int partition5(
+            List<T> list,
+            int left,
+            int right
+    ) {
+        List<T> ts = list.subList(left, right);
+        ts.sort(Comparator.naturalOrder());
+        return (left + right) >>> 1;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/QuickSelectTest.java b/src/test/java/com/thealgorithms/searches/QuickSelectTest.java
new file mode 100644
index 00000000..588b20f5
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/QuickSelectTest.java
@@ -0,0 +1,240 @@
+package com.thealgorithms.searches;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class QuickSelectTest {
+    @Test
+    void quickSelectMinimumOfOneElement() {
+        List<Integer> elements = Collections.singletonList(42);
+        int minimum = QuickSelect.select(elements, 0);
+        assertEquals(42, minimum);
+    }
+
+    @Test
+    void quickSelectMinimumOfTwoElements() {
+        List<Integer> elements1 = Arrays.asList(42, 90);
+        List<Integer> elements2 = Arrays.asList(90, 42);
+
+        int minimum1 = QuickSelect.select(elements1, 0);
+        int minimum2 = QuickSelect.select(elements2, 0);
+
+        assertEquals(42, minimum1);
+        assertEquals(42, minimum2);
+    }
+
+    @Test
+    void quickSelectMinimumOfThreeElements() {
+        List<Integer> elements1 = Arrays.asList(1, 2, 3);
+        List<Integer> elements2 = Arrays.asList(2, 1, 3);
+        List<Integer> elements3 = Arrays.asList(2, 3, 1);
+
+        int minimum1 = QuickSelect.select(elements1, 0);
+        int minimum2 = QuickSelect.select(elements2, 0);
+        int minimum3 = QuickSelect.select(elements3, 0);
+
+        assertEquals(1, minimum1);
+        assertEquals(1, minimum2);
+        assertEquals(1, minimum3);
+    }
+
+    @Test
+    void quickSelectMinimumOfManyElements() {
+        List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
+        int actual = QuickSelect.select(elements, 0);
+        int expected = elements.stream().min(Comparator.naturalOrder()).get();
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    void quickSelectMaximumOfOneElement() {
+        List<Integer> elements = Collections.singletonList(42);
+        int maximum = QuickSelect.select(elements, 0);
+        assertEquals(42, maximum);
+    }
+
+    @Test
+    void quickSelectMaximumOfTwoElements() {
+        List<Integer> elements1 = Arrays.asList(42, 90);
+        List<Integer> elements2 = Arrays.asList(90, 42);
+
+        int maximum1 = QuickSelect.select(elements1, 1);
+        int maximum2 = QuickSelect.select(elements2, 1);
+
+        assertEquals(90, maximum1);
+        assertEquals(90, maximum2);
+    }
+
+    @Test
+    void quickSelectMaximumOfThreeElements() {
+        List<Integer> elements1 = Arrays.asList(1, 2, 3);
+        List<Integer> elements2 = Arrays.asList(2, 1, 3);
+        List<Integer> elements3 = Arrays.asList(2, 3, 1);
+
+        int maximum1 = QuickSelect.select(elements1, 2);
+        int maximum2 = QuickSelect.select(elements2, 2);
+        int maximum3 = QuickSelect.select(elements3, 2);
+
+        assertEquals(3, maximum1);
+        assertEquals(3, maximum2);
+        assertEquals(3, maximum3);
+    }
+
+    @Test
+    void quickSelectMaximumOfManyElements() {
+        List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
+        int actual = QuickSelect.select(elements, NUM_RND_ELEMENTS - 1);
+        int expected = elements.stream().max(Comparator.naturalOrder()).get();
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    void quickSelectMedianOfOneElement() {
+        List<Integer> elements = Collections.singletonList(42);
+        int median = QuickSelect.select(elements, 0);
+        assertEquals(42, median);
+    }
+
+    @Test
+    void quickSelectMedianOfThreeElements() {
+        List<Integer> elements1 = Arrays.asList(1, 2, 3);
+        List<Integer> elements2 = Arrays.asList(2, 1, 3);
+        List<Integer> elements3 = Arrays.asList(2, 3, 1);
+
+        int median1 = QuickSelect.select(elements1, 1);
+        int median2 = QuickSelect.select(elements2, 1);
+        int median3 = QuickSelect.select(elements3, 1);
+
+        assertEquals(2, median1);
+        assertEquals(2, median2);
+        assertEquals(2, median3);
+    }
+
+    @Test
+    void quickSelectMedianOfManyElements() {
+        int medianIndex = NUM_RND_ELEMENTS / 2;
+        List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
+        int actual = QuickSelect.select(elements, medianIndex);
+
+        List<Integer> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(medianIndex), actual);
+    }
+
+    @Test
+    void quickSelect30thPercentileOf10Elements() {
+        List<Integer> elements = generateRandomIntegers(10);
+        int actual = QuickSelect.select(elements, 2);
+
+        List<Integer> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(2), actual);
+    }
+
+    @Test
+    void quickSelect30thPercentileOfManyElements() {
+        int percentile30th = NUM_RND_ELEMENTS / 10 * 3;
+        List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
+        int actual = QuickSelect.select(elements, percentile30th);
+
+        List<Integer> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(percentile30th), actual);
+    }
+
+    @Test
+    void quickSelect70thPercentileOf10Elements() {
+        List<Integer> elements = generateRandomIntegers(10);
+        int actual = QuickSelect.select(elements, 6);
+
+        List<Integer> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(6), actual);
+    }
+
+    @Test
+    void quickSelect70thPercentileOfManyElements() {
+        int percentile70th = NUM_RND_ELEMENTS / 10 * 7;
+        List<Integer> elements = generateRandomIntegers(NUM_RND_ELEMENTS);
+        int actual = QuickSelect.select(elements, percentile70th);
+
+        List<Integer> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(percentile70th), actual);
+    }
+
+    @Test
+    void quickSelectMedianOfThreeCharacters() {
+        List<Character> elements = Arrays.asList('X', 'Z', 'Y');
+        char actual = QuickSelect.select(elements, 1);
+        assertEquals(actual, 'Y');
+    }
+
+    @Test
+    void quickSelectMedianOfManyCharacters() {
+        List<Character> elements = generateRandomCharacters(NUM_RND_ELEMENTS);
+        char actual = QuickSelect.select(elements, NUM_RND_ELEMENTS / 30);
+
+        List<Character> elementsSorted = getSortedCopyOfList(elements);
+        assertEquals(elementsSorted.get(NUM_RND_ELEMENTS / 30), actual);
+    }
+
+    @Test
+    void quickSelectNullList() {
+        NullPointerException exception = assertThrows(
+                NullPointerException.class,
+                () -> QuickSelect.select(null, 0)
+        );
+        String expectedMsg = "The list of elements must not be null.";
+        assertEquals(expectedMsg, exception.getMessage());
+    }
+
+    @Test
+    void quickSelectEmptyList() {
+        List<String> objects = Collections.emptyList();
+        IllegalArgumentException exception = assertThrows(
+                IllegalArgumentException.class,
+                () -> QuickSelect.select(objects, 0)
+        );
+        String expectedMsg = "The list of elements must not be empty.";
+        assertEquals(expectedMsg, exception.getMessage());
+    }
+
+    @Test
+    void quickSelectIndexOutOfLeftBound() {
+        IndexOutOfBoundsException exception = assertThrows(
+                IndexOutOfBoundsException.class,
+                () -> QuickSelect.select(Collections.singletonList(1), -1)
+        );
+        String expectedMsg = "The index must not be negative.";
+        assertEquals(expectedMsg, exception.getMessage());
+    }
+
+    @Test
+    void quickSelectIndexOutOfRightBound() {
+        IndexOutOfBoundsException exception = assertThrows(
+                IndexOutOfBoundsException.class,
+                () -> QuickSelect.select(Collections.singletonList(1), 1)
+        );
+        String expectedMsg = "The index must be less than the number of elements.";
+        assertEquals(expectedMsg, exception.getMessage());
+    }
+
+    private static final int NUM_RND_ELEMENTS = 99;
+    private static final Random RANDOM = new Random(42);
+    private static final int ASCII_A = 0x41;
+    private static final int ASCII_Z = 0x5A;
+
+    private static List<Integer> generateRandomIntegers(int n) {
+        return RANDOM.ints(n).boxed().collect(Collectors.toList());
+    }
+
+    private static List<Character> generateRandomCharacters(int n) {
+        return RANDOM.ints(n, ASCII_A, ASCII_Z)
+                .mapToObj(i -> (char) i)
+                .collect(Collectors.toList());
+    }
+
+    private static <T extends Comparable<T>> List<T> getSortedCopyOfList(List<T> list) {
+        return list.stream().sorted().collect(Collectors.toList());
+    }
+}