Skip to content

Feature quick select #2860

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Dec 8, 2021
Merged

Feature quick select #2860

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
745ea2c
added JUnit 5 Maven dependencies
Dec 5, 2021
1d41a7f
added QuickSelect algorithm + tests
Dec 5, 2021
2954b72
Merge branch 'master' into feature_QuickSelect
siriak Dec 7, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
37 changes: 36 additions & 1 deletion pom.xml
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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>
Expand All @@ -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>
140 changes: 140 additions & 0 deletions src/main/java/com/thealgorithms/searches/QuickSelect.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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;
}
}
Loading