QuickSelect.java

packagecom.thealgorithms.searches;

importjava.util.Collections;
importjava.util.Comparator;
importjava.util.List;
importjava.util.Objects;

/**
 * An implementation of the Quickselect algorithm as described
 * <a href="https://en.wikipedia.org/wiki/Median_of_medians">here</a>.
 */
publicfinalclassQuickSelect {
privateQuickSelect() {
 }

/**
 * 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
 */
publicstatic <TextendsComparable<T>> Tselect(List<T> list, intn) {
Objects.requireNonNull(list, "The list of elements must not be null.");

if (list.isEmpty()) {
Stringmsg = "The list of elements must not be empty.";
thrownewIllegalArgumentException(msg);
 }

if (n < 0) {
Stringmsg = "The index must not be negative.";
thrownewIndexOutOfBoundsException(msg);
 }

if (n >= list.size()) {
Stringmsg = "The index must be less than the number of elements.";
thrownewIndexOutOfBoundsException(msg);
 }

intindex = selectIndex(list, n);
returnlist.get(index);
 }

privatestatic <TextendsComparable<T>> intselectIndex(List<T> list, intn) {
returnselectIndex(list, 0, list.size() - 1, n);
 }

privatestatic <TextendsComparable<T>> intselectIndex(List<T> list, intleft, intright, intn) {
while (true) {
if (left == right) {
returnleft;
 }
intpivotIndex = pivot(list, left, right);
pivotIndex = partition(list, left, right, pivotIndex, n);
if (n == pivotIndex) {
returnn;
 } elseif (n < pivotIndex) {
right = pivotIndex - 1;
 } else {
left = pivotIndex + 1;
 }
 }
 }

privatestatic <TextendsComparable<T>> intpartition(List<T> list, intleft, intright, intpivotIndex, intn) {
TpivotValue = list.get(pivotIndex);
Collections.swap(list, pivotIndex, right);
intstoreIndex = left;

for (inti = left; i < right; i++) {
if (list.get(i).compareTo(pivotValue) < 0) {
Collections.swap(list, storeIndex, i);
storeIndex++;
 }
 }

intstoreIndexEq = storeIndex;

for (inti = 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);
 }

privatestatic <TextendsComparable<T>> intpivot(List<T> list, intleft, intright) {
if (right - left < 5) {
returnpartition5(list, left, right);
 }

for (inti = left; i < right; i += 5) {
intsubRight = i + 4;
if (subRight > right) {
subRight = right;
 }
intmedian5 = partition5(list, i, subRight);
intrightIndex = left + (i - left) / 5;
Collections.swap(list, median5, rightIndex);
 }

intmid = (right - left) / 10 + left + 1;
intrightIndex = left + (right - left) / 5;
returnselectIndex(list, left, rightIndex, mid);
 }

privatestatic <TextendsComparable<T>> intpartition5(List<T> list, intleft, intright) {
List<T> ts = list.subList(left, right);
ts.sort(Comparator.naturalOrder());
return (left + right) >>> 1;
 }
}