Skip to content

Instantly share code, notes, and snippets.

@unnikked
Created July 4, 2015 15:40
Show Gist options
  • Save unnikked/14c19ba13f6a4bfd00a3 to your computer and use it in GitHub Desktop.
Save unnikked/14c19ba13f6a4bfd00a3 to your computer and use it in GitHub Desktop.
A basic implementation of quickselect algorithm in Java. Intentionally unused generics.
import java.util.Arrays;
/**
* quickselect is a selection algorithm to find the kth smallest element in an
* unordered list. Like quicksort, it is efficient in practice and has good
* average-case performance, but has poor worst-case performance. Quickselect
* and variants is the selection algorithm most often used in efficient
* real-world implementations.
*
* Quickselect uses the same overall approach as quicksort, choosing one
* element as a pivot and partitioning the data in two based on the pivot,
* accordingly as less than or greater than the pivot. However, instead of
* recursing into both sides, as in quicksort, quickselect only recurses into
* one side – the side with the element it is searching for. This reduces the
* average complexity from O(n log n) (in quicksort) to O(n) (in quickselect).
*
* As with quicksort, quickselect is generally implemented as an in-place
* algorithm, and beyond selecting the kth element, it also partially sorts
* the data. See selection algorithm for further discussion of the connection
* with sorting.
*
* This is an implementation of: https://en.m.wikipedia.org/wiki/Quickselect
* LICENSE https://creativecommons.org/licenses/by-sa/3.0/
*/
public final class QuickSelect {
/**
* Note the resemblance to quicksort: just as the minimum-based selection
* algorithm is a partial selection sort, this is a partial quicksort,
* generating and partitioning only O(log n) of its O(n) partitions. This
* simple procedure has expected linear performance, and, like quicksort,
* has quite good performance in practice. It is also an in-place
* algorithm, requiring only constant memory overhead, since the tail
* recursion can be eliminated with a loop like this
*/
public static int selectIterative(int[] array, int n) {
return iterative(array, 0, array.length - 1, n);
}
private static int iterative(int[] array, int left, int right, int n) {
if(left == right) {
return array[left];
}
for(;;) {
int pivotIndex = randomPivot(left, right);
pivotIndex = partition(array, left, right, pivotIndex);
if(n == pivotIndex) {
return array[n];
} else if(n < pivotIndex) {
right = pivotIndex - 1;
} else {
left = pivotIndex + 1;
}
}
}
/**
* In quicksort, we recursively sort both branches, leading to best-case
* Ω(n log n) time. However, when doing selection, we already know which
* partition our desired element lies in, since the pivot is in its final
* sorted position, with all those preceding it in an unsorted order and
* all those following it in an unsorted order. Therefore, a single
* recursive call locates the desired element in the correct partition, and
* we build upon this for quickselect.
*/
public static int selectRecursive(int[] array, int n) {
return recursive(array, 0, array.length - 1, n);
}
// Returns the n-th smallest element of list within left..right inclusive
// (i.e. left <= n <= right).
// The size of the list is not changing with each recursion.
// Thus, n does not need to be updated with each round.
private static int recursive(int[] array, int left, int right, int n) {
if (left == right) { // If the list contains only one element,
return array[left]; // return that element
}
// select a pivotIndex between left and right
int pivotIndex = randomPivot(left, right);
pivotIndex = partition(array, left, right, pivotIndex);
// The pivot is in its final sorted position
if (n == pivotIndex) {
return array[n];
} else if (n < pivotIndex) {
return recursive(array, left, pivotIndex - 1, n);
} else {
return recursive(array, pivotIndex + 1, right, n);
}
}
/**
* In quicksort, there is a subprocedure called partition that can, in
* linear time, group a list (ranging from indices left to right) into two
* parts, those less than a certain element, and those greater than or
* equal to the element. Here is pseudocode that performs a partition about
* the element list[pivotIndex]
*/
private static int partition(int[] array, int left, int right, int pivotIndex) {
int pivotValue = array[pivotIndex];
swap(array, pivotIndex, right); // move pivot to end
int storeIndex = left;
for(int i = left; i < right; i++) {
if(array[i] < pivotValue) {
swap(array, storeIndex, i);
storeIndex++;
}
}
swap(array, right, storeIndex); // Move pivot to its final place
return storeIndex;
}
private static void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
private static int randomPivot(int left, int right) {
return left + (int) Math.floor(Math.random() * (right - left + 1));
}
public static void main(String[] args) {
int[] array = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
for(int i = 0; i < array.length; i++) {
System.out.println(selectIterative(array, i));
}
for(int i = 0; i < array.length; i++) {
System.out.println(selectRecursive(array, i));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment