Skip to content

Commit 66d8d51

Browse files
Nils-GoldmannNils Goldmannsiriak
authored
Add Quick Select (#2860)
Co-authored-by: Nils Goldmann <goldman09@mi.fu-berlin.de> Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent 8e01cd4 commit 66d8d51

File tree

3 files changed

+416
-1
lines changed

3 files changed

+416
-1
lines changed

‎pom.xml

Lines changed: 36 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
<?xml version="1.0" encoding="UTF-8"?>
2-
<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">
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
35
<modelVersion>4.0.0</modelVersion>
46
<groupId>com.thealgorithms</groupId>
57
<artifactId>Java</artifactId>
@@ -10,4 +12,37 @@
1012
<maven.compiler.source>17</maven.compiler.source>
1113
<maven.compiler.target>17</maven.compiler.target>
1214
</properties>
15+
16+
<dependencyManagement>
17+
<dependencies>
18+
<dependency>
19+
<groupId>org.junit</groupId>
20+
<artifactId>junit-bom</artifactId>
21+
<version>5.8.2</version>
22+
<type>pom</type>
23+
<scope>import</scope>
24+
</dependency>
25+
</dependencies>
26+
</dependencyManagement>
27+
28+
<dependencies>
29+
<dependency>
30+
<groupId>org.junit.jupiter</groupId>
31+
<artifactId>junit-jupiter</artifactId>
32+
<scope>test</scope>
33+
</dependency>
34+
</dependencies>
35+
36+
<build>
37+
<plugins>
38+
<plugin>
39+
<artifactId>maven-compiler-plugin</artifactId>
40+
<version>3.8.1</version>
41+
</plugin>
42+
<plugin>
43+
<artifactId>maven-surefire-plugin</artifactId>
44+
<version>2.22.2</version>
45+
</plugin>
46+
</plugins>
47+
</build>
1348
</project>

‎src/main/java/com/thealgorithms/searches/QuickSelect.java

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
package com.thealgorithms.searches;
2+
3+
import java.util.*;
4+
5+
/**
6+
* An implementation of the Quickselect algorithm as described
7+
* <a href="https://en.wikipedia.org/wiki/Median_of_medians">here</a>.
8+
*/
9+
public final class QuickSelect {
10+
11+
/**
12+
* Selects the {@code n}-th largest element of {@code list}, i.e. the element that would
13+
* be at index n if the list was sorted.
14+
* <p>
15+
* Calling this function might change the order of elements in {@code list}.
16+
*
17+
* @param list the list of elements
18+
* @param n the index
19+
* @param <T> the type of list elements
20+
* @return the n-th largest element in the list
21+
* @throws IndexOutOfBoundsException if n is less than 0 or greater or equal to
22+
* the number of elements in the list
23+
* @throws IllegalArgumentException if the list is empty
24+
* @throws NullPointerException if {@code list} is null
25+
*/
26+
public static <T extends Comparable<T>> T select(List<T> list, int n) {
27+
Objects.requireNonNull(list, "The list of elements must not be null.");
28+
29+
if (list.size() == 0) {
30+
String msg = "The list of elements must not be empty.";
31+
throw new IllegalArgumentException(msg);
32+
}
33+
34+
if (n < 0) {
35+
String msg = "The index must not be negative.";
36+
throw new IndexOutOfBoundsException(msg);
37+
}
38+
39+
if (n >= list.size()) {
40+
String msg = "The index must be less than the number of elements.";
41+
throw new IndexOutOfBoundsException(msg);
42+
}
43+
44+
int index = selectIndex(list, n);
45+
return list.get(index);
46+
}
47+
48+
private static <T extends Comparable<T>> int selectIndex(List<T> list, int n) {
49+
return selectIndex(list, 0, list.size() - 1, n);
50+
}
51+
52+
private static <T extends Comparable<T>> int selectIndex(
53+
List<T> list,
54+
int left,
55+
int right,
56+
int n
57+
) {
58+
while (true) {
59+
if (left == right)
60+
return left;
61+
int pivotIndex = pivot(list, left, right);
62+
pivotIndex = partition(list, left, right, pivotIndex, n);
63+
if (n == pivotIndex) {
64+
return n;
65+
} else if (n < pivotIndex) {
66+
right = pivotIndex - 1;
67+
} else {
68+
left = pivotIndex + 1;
69+
}
70+
}
71+
}
72+
73+
private static <T extends Comparable<T>> int partition(
74+
List<T> list,
75+
int left,
76+
int right,
77+
int pivotIndex,
78+
int n
79+
) {
80+
T pivotValue = list.get(pivotIndex);
81+
Collections.swap(list, pivotIndex, right);
82+
int storeIndex = left;
83+
84+
for (int i = left; i < right; i++) {
85+
if (list.get(i).compareTo(pivotValue) < 0) {
86+
Collections.swap(list, storeIndex, i);
87+
storeIndex++;
88+
}
89+
}
90+
91+
int storeIndexEq = storeIndex;
92+
93+
for (int i = storeIndex; i < right; i++) {
94+
if (list.get(i).compareTo(pivotValue) == 0) {
95+
Collections.swap(list, storeIndexEq, i);
96+
storeIndexEq++;
97+
}
98+
}
99+
100+
Collections.swap(list, right, storeIndexEq);
101+
102+
return (n < storeIndex)
103+
? storeIndex
104+
: Math.min(n, storeIndexEq);
105+
}
106+
107+
private static <T extends Comparable<T>> int pivot(
108+
List<T> list,
109+
int left,
110+
int right
111+
) {
112+
if (right - left < 5) {
113+
return partition5(list, left, right);
114+
}
115+
116+
for (int i = left; i < right; i += 5) {
117+
int subRight = i + 4;
118+
if (subRight > right) {
119+
subRight = right;
120+
}
121+
int median5 = partition5(list, i, subRight);
122+
int rightIndex = left + (i - left) / 5;
123+
Collections.swap(list, median5, rightIndex);
124+
}
125+
126+
int mid = (right - left) / 10 + left + 1;
127+
int rightIndex = left + (right - left) / 5;
128+
return selectIndex(list, left, rightIndex, mid);
129+
}
130+
131+
private static <T extends Comparable<T>> int partition5(
132+
List<T> list,
133+
int left,
134+
int right
135+
) {
136+
List<T> ts = list.subList(left, right);
137+
ts.sort(Comparator.naturalOrder());
138+
return (left + right) >>> 1;
139+
}
140+
}

0 commit comments

Comments
 (0)