Quickselect algorithm

From Rosetta Code
Jump to: navigation, search
Task
Quickselect algorithm
You are encouraged to solve this task according to the task description, using any language you may know.

Use the quickselect algorithm on the vector

[9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page.

  • Note: Quicksort has a separate task.

Contents

[edit] AutoHotkey

Works with: AutoHotkey_L
(AutoHotkey1.1+)

A direct implementation of the Wikipedia pseudo-code.

MyList := [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
Loop, 10
Out .= Select(MyList, 1, MyList.MaxIndex(), A_Index) (A_Index = MyList.MaxIndex() ? "" : ", ")
MsgBox, % Out
return
 
Partition(List, Left, Right, PivotIndex) {
PivotValue := List[PivotIndex]
, Swap(List, pivotIndex, Right)
, StoreIndex := Left
, i := Left - 1
Loop, % Right - Left
if (List[j := i + A_Index] <= PivotValue)
Swap(List, StoreIndex, j)
, StoreIndex++
Swap(List, Right, StoreIndex)
return StoreIndex
}
 
Select(List, Left, Right, n) {
if (Left = Right)
return List[Left]
Loop {
PivotIndex := (Left + Right) // 2
, PivotIndex := Partition(List, Left, Right, PivotIndex)
if (n = PivotIndex)
return List[n]
else if (n < PivotIndex)
Right := PivotIndex - 1
else
Left := PivotIndex + 1
}
}
 
Swap(List, i1, i2) {
t := List[i1]
, List[i1] := List[i2]
, List[i2] := t
}

Output:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 

[edit] C

#include <stdio.h>
#include <string.h>
 
int qselect(int *v, int len, int k)
{
# define SWAP(a, b) { tmp = v[a]; v[a] = v[b]; v[b] = tmp; }
int i, st, tmp;
 
for (st = i = 0; i < len - 1; i++) {
if (v[i] > v[len-1]) continue;
SWAP(i, st);
st++;
}
 
SWAP(len-1, st);
 
return k == st ?v[st]
:st > k ? qselect(v, st, k)
: qselect(v + st, len - st, k - st);
}
 
int main(void)
{
# define N (sizeof(x)/sizeof(x[0]))
int x[] = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
int y[N];
 
int i;
for (i = 0; i < 10; i++) {
memcpy(y, x, sizeof(x)); // qselect modifies array
printf("%d: %d\n", i, qselect(y, 10, i));
}
 
return 0;
}
Output:
0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9

[edit] C++

Library

It is already provided in the standard library as std::nth_element(). Although the standard does not explicitly mention what algorithm it must use, the algorithm partitions the sequence into those less than the nth element to the left, and those greater than the nth element to the right, like quickselect; the standard also guarantees that the complexity is "linear on average", which fits quickselect.

#include <algorithm>
#include <iostream>
 
int main() {
for (int i = 0; i < 10; i++) {
int a[] = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
std::nth_element(a, a + i, a + sizeof(a)/sizeof(*a));
std::cout << a[i];
if (i < 9) std::cout << ", ";
}
std::cout << std::endl;
 
return 0;
}
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Implementation

A more explicit implementation:

#include <iterator>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <ctime>
#include <iostream>
 
template <typename Iterator>
Iterator select(Iterator begin, Iterator end, int n) {
typedef typename std::iterator_traits<Iterator>::value_type T;
while (true) {
Iterator pivotIt = begin + std::rand() % std::distance(begin, end);
std::iter_swap(pivotIt, end-1); // Move pivot to end
pivotIt = std::partition(begin, end-1, std::bind2nd(std::less<T>(), *(end-1)));
std::iter_swap(end-1, pivotIt); // Move pivot to its final place
if (n == pivotIt - begin) {
return pivotIt;
} else if (n < pivotIt - begin) {
end = pivotIt;
} else {
n -= pivotIt+1 - begin;
begin = pivotIt+1;
}
}
}
 
int main() {
std::srand(std::time(NULL));
for (int i = 0; i < 10; i++) {
int a[] = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
std::cout << *select(a, a + sizeof(a)/sizeof(*a), i);
if (i < 9) std::cout << ", ";
}
std::cout << std::endl;
 
return 0;
}
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[edit] C#

Two different implementations - one that returns only one element from the array (Nth smallest element) and second implementation that returns IEnumnerable that enumerates through element until Nth smallest element.

// ----------------------------------------------------------------------------------------------
//
// Program.cs - QuickSelect
//
// ----------------------------------------------------------------------------------------------
 
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace QuickSelect
{
internal static class Program
{
#region Static Members
 
private static void Main()
{
var inputArray = new[] {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
// Loop 10 times
Console.WriteLine( "Loop quick select 10 times." );
for( var i = 0 ; i < 10 ; i++ )
{
Console.Write( inputArray.NthSmallestElement( i ) );
if( i < 9 )
Console.Write( ", " );
}
Console.WriteLine();
 
// And here is then more effective way to get N smallest elements from vector in order by using quick select algorithm
// Basically we are here just sorting array (taking 10 smallest from array which length is 10)
Console.WriteLine( "Just sort 10 elements." );
Console.WriteLine( string.Join( ", ", inputArray.TakeSmallest( 10 ).OrderBy( v => v ).Select( v => v.ToString() ).ToArray() ) );
// Here we are actually doing quick select once by taking only 4 smallest from array.
Console.WriteLine( "Get 4 smallest and sort them." );
Console.WriteLine( string.Join( ", ", inputArray.TakeSmallest( 4 ).OrderBy( v => v ).Select( v => v.ToString() ).ToArray() ) );
Console.WriteLine( "< Press any key >" );
Console.ReadKey();
}
 
#endregion
}
 
internal static class ArrayExtension
{
#region Static Members
 
/// <summary>
/// Return specified number of smallest elements from array.
/// </summary>
/// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
/// <param name="array">The array to return elemnts from.</param>
/// <param name="count">The number of smallest elements to return. </param>
/// <returns>An IEnumerable(T) that contains the specified number of smallest elements of the input array. Returned elements are NOT sorted.</returns>
public static IEnumerable<T> TakeSmallest<T>( this T[] array, int count ) where T : IComparable<T>
{
if( count < 0 )
throw new ArgumentOutOfRangeException( "count", "Count is smaller than 0." );
if( count == 0 )
return new T[0];
if( array.Length <= count )
return array;
 
return QuickSelectSmallest( array, count - 1 ).Take( count );
}
 
/// <summary>
/// Returns N:th smallest element from the array.
/// </summary>
/// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
/// <param name="array">The array to return elemnt from.</param>
/// <param name="n">Nth element. 0 is smallest element, when array.Length - 1 is largest element.</param>
/// <returns>N:th smalles element from the array.</returns>
public static T NthSmallestElement<T>( this T[] array, int n ) where T : IComparable<T>
{
if( n < 0 || n > array.Length - 1 )
throw new ArgumentOutOfRangeException( "n", n, string.Format( "n should be between 0 and {0} it was {1}.", array.Length - 1, n ) );
if( array.Length == 0 )
throw new ArgumentException( "Array is empty.", "array" );
if( array.Length == 1 )
return array[ 0 ];
 
return QuickSelectSmallest( array, n )[ n ];
}
 
/// <summary>
/// Partially sort array such way that elements before index position n are smaller or equal than elemnt at position n. And elements after n are larger or equal.
/// </summary>
/// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
/// <param name="input">The array which elements are being partially sorted. This array is not modified.</param>
/// <param name="n">Nth smallest element.</param>
/// <returns>Partially sorted array.</returns>
private static T[] QuickSelectSmallest<T>( T[] input, int n ) where T : IComparable<T>
{
// Let's not mess up with our input array
// For very large arrays - we should optimize this somehow - or just mess up with our input
var partiallySortedArray = (T[]) input.Clone();
 
// Initially we are going to execute quick select to entire array
var startIndex = 0;
var endIndex = input.Length - 1;
 
// Selecting initial pivot
// Maybe we are lucky and array is sorted initially?
var pivotIndex = n;
 
// Loop until there is nothing to loop (this actually shouldn't happen - we should find our value before we run out of values)
var r = new Random();
while( endIndex > startIndex )
{
pivotIndex = QuickSelectPartition( partiallySortedArray, startIndex, endIndex, pivotIndex );
if( pivotIndex == n )
// We found our n:th smallest value - it is stored to pivot index
break;
if( pivotIndex > n )
// Array before our pivot index have more elements that we are looking for
endIndex = pivotIndex - 1;
else
// Array before our pivot index has less elements that we are looking for
startIndex = pivotIndex + 1;
 
// Omnipotent beings don't need to roll dices - but we do...
// Randomly select a new pivot index between end and start indexes (there are other methods, this is just most brutal and simplest)
pivotIndex = r.Next( startIndex, endIndex );
}
return partiallySortedArray;
}
 
/// <summary>
/// Sort elements in sub array between startIndex and endIndex, such way that elements smaller than or equal with value initially stored to pivot index are before
/// new returned pivot value index.
/// </summary>
/// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
/// <param name="array">The array that is being sorted.</param>
/// <param name="startIndex">Start index of sub array.</param>
/// <param name="endIndex">End index of sub array.</param>
/// <param name="pivotIndex">Pivot index.</param>
/// <returns>New pivot index. Value that was initially stored to <paramref name="pivotIndex"/> is stored to this newly returned index. All elements before this index are
/// either smaller or equal with pivot value. All elements after this index are larger than pivot value.</returns>
/// <remarks>This method modifies paremater array.</remarks>
private static int QuickSelectPartition<T>( this T[] array, int startIndex, int endIndex, int pivotIndex ) where T : IComparable<T>
{
var pivotValue = array[ pivotIndex ];
// Initially we just assume that value in pivot index is largest - so we move it to end (makes also for loop more straight forward)
array.Swap( pivotIndex, endIndex );
for( var i = startIndex ; i < endIndex ; i++ )
{
if( array[ i ].CompareTo( pivotValue ) > 0 )
continue;
 
// Value stored to i was smaller than or equal with pivot value - let's move it to start
array.Swap( i, startIndex );
// Move start one index forward
startIndex++;
}
// Start index is now pointing to index where we should store our pivot value from end of array
array.Swap( endIndex, startIndex );
return startIndex;
}
 
private static void Swap<T>( this T[] array, int index1, int index2 )
{
if( index1 == index2 )
return;
 
var temp = array[ index1 ];
array[ index1 ] = array[ index2 ];
array[ index2 ] = temp;
}
 
#endregion
}
}
Output:
Loop quick select 10 times.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Just sort 10 elements.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Get 4 smallest and sort them.
0, 1, 2, 3
< Press any key >

[edit] COBOL

The following is in the Managed COBOL dialect:

Works with: Visual COBOL
       CLASS-ID MainProgram.
 
METHOD-ID Partition STATIC USING T.
CONSTRAINTS.
CONSTRAIN T IMPLEMENTS type IComparable.
 
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 pivot-val T.
 
PROCEDURE DIVISION USING VALUE arr AS T OCCURS ANY,
left-idx AS BINARY-LONG, right-idx AS BINARY-LONG,
pivot-idx AS BINARY-LONG
RETURNING ret AS BINARY-LONG.
MOVE arr (pivot-idx) TO pivot-val
INVOKE self::Swap(arr, pivot-idx, right-idx)
DECLARE store-idx AS BINARY-LONG = left-idx
PERFORM VARYING i AS BINARY-LONG FROM left-idx BY 1
UNTIL i > right-idx
IF arr (i) < pivot-val
INVOKE self::Swap(arr, i, store-idx)
ADD 1 TO store-idx
END-IF
END-PERFORM
INVOKE self::Swap(arr, right-idx, store-idx)
 
MOVE store-idx TO ret
END METHOD.
 
METHOD-ID Quickselect STATIC USING T.
CONSTRAINTS.
CONSTRAIN T IMPLEMENTS type IComparable.
 
PROCEDURE DIVISION USING VALUE arr AS T OCCURS ANY,
left-idx AS BINARY-LONG, right-idx AS BINARY-LONG,
n AS BINARY-LONG
RETURNING ret AS T.
IF left-idx = right-idx
MOVE arr (left-idx) TO ret
GOBACK
END-IF
 
DECLARE rand AS TYPE Random = NEW Random()
DECLARE pivot-idx AS BINARY-LONG = rand::Next(left-idx, right-idx)
DECLARE pivot-new-idx AS BINARY-LONG
= self::Partition(arr, left-idx, right-idx, pivot-idx)
DECLARE pivot-dist AS BINARY-LONG = pivot-new-idx - left-idx + 1
 
EVALUATE TRUE
WHEN pivot-dist = n
MOVE arr (pivot-new-idx) TO ret
 
WHEN n < pivot-dist
INVOKE self::Quickselect(arr, left-idx, pivot-new-idx - 1, n)
RETURNING ret
 
WHEN OTHER
INVOKE self::Quickselect(arr, pivot-new-idx + 1, right-idx,
n - pivot-dist) RETURNING ret
END-EVALUATE
END METHOD.
 
METHOD-ID Swap STATIC USING T.
CONSTRAINTS.
CONSTRAIN T IMPLEMENTS type IComparable.
 
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 temp T.
 
PROCEDURE DIVISION USING arr AS T OCCURS ANY,
VALUE idx-1 AS BINARY-LONG, idx-2 AS BINARY-LONG.
IF idx-1 <> idx-2
MOVE arr (idx-1) TO temp
MOVE arr (idx-2) TO arr (idx-1)
MOVE temp TO arr (idx-2)
END-IF
END METHOD.
 
METHOD-ID Main STATIC.
PROCEDURE DIVISION.
DECLARE input-array AS BINARY-LONG OCCURS ANY
= TABLE OF BINARY-LONG(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
DISPLAY "Loop quick select 10 times."
PERFORM VARYING i AS BINARY-LONG FROM 1 BY 1 UNTIL i > 10
DISPLAY self::Quickselect(input-array, 1, input-array::Length, i)
NO ADVANCING
 
IF i < 10
DISPLAY ", " NO ADVANCING
END-IF
END-PERFORM
DISPLAY SPACE
END METHOD.
END CLASS.

[edit] D

[edit] Standard Version

This could use a different algorithm:

void main() {
import std.stdio, std.algorithm;
 
auto a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
foreach (immutable i; 0 .. a.length) {
a.topN(i);
write(a[i], " ");
}
}
Output:
0 1 2 3 4 5 6 7 8 9 

[edit] Array Version

Translation of: Java
import std.stdio, std.random, std.algorithm, std.range;
 
T quickSelect(T)(T[] arr, size_t n)
in {
assert(n < arr.length);
} body {
static size_t partition(T[] sub, in size_t pivot) pure nothrow
in {
assert(!sub.empty);
assert(pivot < sub.length);
} body {
auto pivotVal = sub[pivot];
sub[pivot].swap(sub.back);
size_t storeIndex = 0;
foreach (ref si; sub[0 .. $ - 1]) {
if (si < pivotVal) {
si.swap(sub[storeIndex]);
storeIndex++;
}
}
sub.back.swap(sub[storeIndex]);
return storeIndex;
}
 
size_t left = 0;
size_t right = arr.length - 1;
while (right > left) {
assert(left < arr.length);
assert(right < arr.length);
immutable pivotIndex = left + partition(arr[left .. right + 1],
uniform(0U, right - left + 1));
if (pivotIndex - left == n) {
right = left = pivotIndex;
} else if (pivotIndex - left < n) {
n -= pivotIndex - left + 1;
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
 
return arr[left];
}
 
void main() {
auto a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
a.length.iota.map!(i => a.quickSelect(i)).writeln;
}
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] F#

Translation of: Haskell
 
let rec quickselect k list =
match list with
| [] -> failwith "Cannot take largest element of empty list."
| [a] -> a
| x::xs ->
let (ys, zs) = List.partition (fun arg -> arg < x) xs
let l = List.length ys
if k < l then quickselect k ys
elif k > l then quickselect (k-l-1) zs
else x
//end quickselect
 
[<EntryPoint>]
let main args =
let v = [9; 8; 7; 6; 5; 0; 1; 2; 3; 4]
printfn "%A" [for i in 0..(List.length v - 1) -> quickselect i v]
0
 
Output:
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

[edit] Go

package main
 
import "fmt"
 
func quickselect(list []int, k int) int {
for {
// partition
px := len(list) / 2
pv := list[px]
last := len(list) - 1
list[px], list[last] = list[last], list[px]
i := 0
for j := 0; j < last; j++ {
if list[j] < pv {
list[i], list[j] = list[j], list[i]
i++
}
}
// select
if i == k {
return pv
}
if k < i {
list = list[:i]
} else {
list[i], list[last] = list[last], list[i]
list = list[i+1:]
k -= i + 1
}
}
}
 
func main() {
for i := 0; ; i++ {
v := []int{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
if i == len(v) {
return
}
fmt.Println(quickselect(v, i))
}
}
Output:
0
1
2
3
4
5
6
7
8
9

A more generic version that works for any container that conforms to sort.Interface:

package main
 
import (
"fmt"
"sort"
"math/rand"
)
 
func partition(a sort.Interface, first int, last int, pivotIndex int) int {
a.Swap(first, pivotIndex) // move it to beginning
left := first+1
right := last
for left <= right {
for left <= last && a.Less(left, first) {
left++
}
for right >= first && a.Less(first, right) {
right--
}
if left <= right {
a.Swap(left, right)
left++
right--
}
}
a.Swap(first, right) // swap into right place
return right
}
 
func quickselect(a sort.Interface, n int) int {
first := 0
last := a.Len()-1
for {
pivotIndex := partition(a, first, last,
rand.Intn(last - first + 1) + first)
if n == pivotIndex {
return pivotIndex
} else if n < pivotIndex {
last = pivotIndex-1
} else {
first = pivotIndex+1
}
}
panic("bad index")
}
 
func main() {
for i := 0; ; i++ {
v := []int{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
if i == len(v) {
return
}
fmt.Println(v[quickselect(sort.IntSlice(v), i)])
}
}
Output:
0
1
2
3
4
5
6
7
8
9

[edit] Haskell

import Data.List (partition)
 
quickselect :: Ord a => Int -> [a] -> a
quickselect k (x:xs) | k < l = quickselect k ys
| k > l = quickselect (k-l-1) zs
| otherwise = x
where (ys, zs) = partition (< x) xs
l = length ys
 
main :: IO ()
main = do
let v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print $ map (\i -> quickselect i v) [0 .. length v-1]
Output:
[0,1,2,3,4,5,6,7,8,9]

[edit] Icon and Unicon

The following works in both languages.

procedure main(A)
every writes(" ",select(1 to *A, A, 1, *A)|"\n")
end
 
procedure select(k,A,min,max)
repeat {
pNI := partition(?(max-min)+min, A, min, max)
pD := pNI - min + 1
if pD = k then return A[pNI]
if k < pD then max := pNI-1
else (k -:= pD, min := pNI+1)
}
end
 
procedure partition(pivot,A,min,max)
pV := (A[max] :=: A[pivot])
sI := min
every A[i := min to max-1] <= pV do (A[sI] :=: A[i], sI +:= 1)
A[max] :=: A[sI]
return sI
end

Sample run:

->qs 9 8 7 6 5 0 1 2 3 4
 0 1 2 3 4 5 6 7 8 9 
->

[edit] J

Caution: as defined, we should expect performance on this task to be bad. Quickselect is optimized for selecting a single element from a list, with best-case performance of O(n) and worst case performance of O(n^2). If we use it to select most of the items from a list, the overall task performance will be O(n^2) best case and O(n^3) worst case. If we really wanted to perform this task efficiently, we would first sort the list and then extract the desired elements. But we do not really want to be efficient here, and maybe that is the point.

Further caution: this task asks us to select "the first, second, third, ... up to the tenth largest member of the vector". But we also cannot know, apriori, what value is the first, second, third, ... largest member. So to accomplish this task we are first going to have to sort the list. But We Will Use Quickselect - that is the specification, after all. Perhaps this task should be taken as an illustration of how silly specifications can sometimes be. We need to have a good sense of humor, after all.

Another caution: quick select simply selects a value that matches. So in the simple case it's an identity operation. When we select a 5 from a list, we get a 5 back out. We can imagine that there might be cases where the thing we get back out is a more complicated data structure. But whether that is really efficient, or not, depends on other factors.

Final caution: a brute-force linear scan of a list is O(n) best case and O(n) worst case. A binary search on an ordered list tends to be faster. So when you hear someone talking about efficiency, you might want to ask "efficient at what?" In this case, I think there might be room for further clarification of that issue (but that makes this a good object lesson - in the real world there are many examples of presentations of ideas which sound great but where other alternatives might be significantly better).

With that out of the way, here's a pedantic (and laughably inefficient) implementation of quickselect:

quickselect=:4 :0
if. 0=#y do. _ return. end.
n=.?#y
m=.n{y
if. x < m do.
x quickselect (m>y)#y
else.
if. x > m do.
x quickselect (m<y)#y
else.
m
end.
end.
)

"Proof" that it works:

   8 quickselect 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
8

And, the required task example:

   ((10 {./:~) quickselect"0 1 ]) 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
0 1 2 3 4 5 6 7 8 9

(Insert here: puns involving greater transparency, the emperor's new clothes, burlesque and maybe the dance of the seven veils.)

[edit] Java

import java.util.Random;
 
public class QuickSelect {
 
private static <E extends Comparable<? super E>> int partition(E[] arr, int left, int right, int pivot) {
E pivotVal = arr[pivot];
swap(arr, pivot, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i].compareTo(pivotVal) < 0) {
swap(arr, i, storeIndex);
storeIndex++;
}
}
swap(arr, right, storeIndex);
return storeIndex;
}
 
private static <E extends Comparable<? super E>> E select(E[] arr, int n) {
int left = 0;
int right = arr.length - 1;
Random rand = new Random();
while (right >= left) {
int pivotIndex = partition(arr, left, right, rand.nextInt(right - left + 1) + left);
if (pivotIndex == n) {
return arr[pivotIndex];
} else if (pivotIndex < n) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
return null;
}
 
private static void swap(Object[] arr, int i1, int i2) {
if (i1 != i2) {
Object temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
}
 
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
Integer[] input = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
System.out.print(select(input, i));
if (i < 9) System.out.print(", ");
}
System.out.println();
}
 
}
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[edit] jq

Works with: jq version 1.4
# Emit the k-th smallest item in the input array,
# or nothing if k is too small or too large.
# The smallest corresponds to k==1.
# The input array may hold arbitrary JSON entities, including null.
def quickselect(k):
 
def partition(pivot):
reduce .[] as $x
# state: [less, other]
( [ [], [] ]; # two empty arrays:
if $x < pivot
then .[0] += [$x] # add x to less
else .[1] += [$x] # add x to other
end
);
 
# recursive inner function has arity 0 for efficiency
def qs: # state: [kn, array] where kn counts from 0
.[0] as $kn
| .[1] as $a
| $a[0] as $pivot
| ($a[1:] | partition($pivot)) as $p
| $p[0] as $left
| ($left|length) as $ll
| if $kn == $ll then $pivot
elif $kn < $ll then [$kn, $left] | qs
else [$kn - $ll - 1, $p[1] ] | qs
end;
 
if length < k or k <= 0 then empty else [k-1, .] | qs end;

Example: Notice that values of k that are too large or too small generate nothing.

(0, 12, range(1;11)) as $k
| [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] | quickselect($k)
| "k=\($k) => \(.)"
Output:
$ jq -n -r -f quickselect.jq
k=1 => 0
k=2 => 1
k=3 => 2
k=4 => 3
k=5 => 4
k=6 => 5
k=7 => 6
k=8 => 7
k=9 => 8
k=10 => 9
$

[edit] NetRexx

/* NetRexx */
options replace format comments java crossref symbols nobinary
/** @see <a href="http://en.wikipedia.org/wiki/Quickselect">http://en.wikipedia.org/wiki/Quickselect</a> */
 
runSample(arg)
return
 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
method qpartition(list, ileft, iright, pivotIndex) private static
pivotValue = list[pivotIndex]
list = swap(list, pivotIndex, iright) -- Move pivot to end
storeIndex = ileft
loop i_ = ileft to iright - 1
if list[i_] <= pivotValue then do
list = swap(list, storeIndex, i_)
storeIndex = storeIndex + 1
end
end i_
list = swap(list, iright, storeIndex) -- Move pivot to its final place
return storeIndex
 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
method qselectInPlace(list, k_, ileft = -1, iright = -1) public static
if ileft = -1 then ileft = 1
if iright = -1 then iright = list[0]
 
loop label inplace forever
pivotIndex = Random().nextInt(iright - ileft + 1) + ileft -- select pivotIndex between left and right
pivotNewIndex = qpartition(list, ileft, iright, pivotIndex)
pivotDist = pivotNewIndex - ileft + 1
select
when pivotDist = k_ then do
returnVal = list[pivotNewIndex]
leave inplace
end
when k_ < pivotDist then
iright = pivotNewIndex - 1
otherwise do
k_ = k_ - pivotDist
ileft = pivotNewIndex + 1
end
end
end inplace
return returnVal
 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
method swap(list, i1, i2) private static
if i1 \= i2 then do
t1 = list[i1]
list[i1] = list[i2]
list[i2] = t1
end
return list
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
parse arg samplelist
if samplelist = '' | samplelist = '.' then samplelist = 9 8 7 6 5 0 1 2 3 4
items = samplelist.words
say 'Input:'
say ' 'samplelist.space(1, ',').changestr(',', ', ')
say
 
say 'Using in-place version of the algorithm:'
iv = ''
loop k_ = 1 to items
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
end k_
say ' 'iv.space(1, ',').changestr(',', ', ')
say
 
say 'Find the 4 smallest:'
iv = ''
loop k_ = 1 to 4
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
end k_
say ' 'iv.space(1, ',').changestr(',', ', ')
say
 
say 'Find the 3 largest:'
iv = ''
loop k_ = items - 2 to items
iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
end k_
say ' 'iv.space(1, ',').changestr(',', ', ')
say
 
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method buildIndexedString(samplelist) private static
list = 0
list[0] = samplelist.words()
loop k_ = 1 to list[0]
list[k_] = samplelist.word(k_)
end k_
return list
 
Output:
Input:
    9, 8, 7, 6, 5, 0, 1, 2, 3, 4

Using in-place version of the algorithm:
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Find the 4 smallest:
    0, 1, 2, 3

Find the 3 largest:
    7, 8, 9

[edit] Nimrod

proc qselect[T](a: var openarray[T]; k: int, inl = 0, inr = -1): T =
var r = if inr >= 0: inr else: a.high
var st = 0
for i in 0 .. < r:
if a[i] > a[r]: continue
swap a[i], a[st]
inc st
 
swap a[r], a[st]
 
if k == st: a[st]
elif st > k: qselect(a, k, 0, st - 1)
else: qselect(a, k, st, inr)
 
let x = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
 
for i in 0..9:
var y = x
echo i, ": ", qselect(y, i)

Output:

0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9

[edit] OCaml

let rec quickselect k = function
[] -> failwith "empty"
| x :: xs -> let ys, zs = List.partition ((>) x) xs in
let l = List.length ys in
if k < l then
quickselect k ys
else if k > l then
quickselect (k-l-1) zs
else
x

Usage:

# let v = [9; 8; 7; 6; 5; 0; 1; 2; 3; 4];;
val v : int list = [9; 8; 7; 6; 5; 0; 1; 2; 3; 4]
# Array.init 10 (fun i -> quickselect i v);;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]

[edit] PARI/GP

part(list, left, right, pivotIndex)={
my(pivotValue=list[pivotIndex],storeIndex=left,t);
t=list[pivotIndex];
list[pivotIndex]=list[right];
list[right]=t;
for(i=left,right-1,
if(list[i] <= pivotValue,
t=list[storeIndex];
list[storeIndex]=list[i];
list[i]=t;
storeIndex++
)
);
t=list[right];
list[right]=list[storeIndex];
list[storeIndex]=t;
storeIndex
};
quickselect(list, left, right, n)={
if(left==right,return(list[left]));
my(pivotIndex=part(list, left, right, random(right-left)+left));
if(pivotIndex==n,return(list[n]));
if(n < pivotIndex,
quickselect(list, left, pivotIndex - 1, n)
,
quickselect(list, pivotIndex + 1, right, n)
)
};

[edit] Perl

my @list = qw(9 8 7 6 5 0 1 2 3 4);
print join ' ', map { qselect(\@list, $_) } 1 .. 10 and print "\n";
 
sub qselect
{
my ($list, $k) = @_;
my $pivot = @$list[int rand @{ $list } - 1];
my @left = grep { $_ < $pivot } @$list;
my @right = grep { $_ > $pivot } @$list;
if ($k <= @left)
{
return qselect(\@left, $k);
}
elsif ($k > @left + 1)
{
return qselect(\@right, $k - @left - 1);
}
else { $pivot }
}
Output:
0 1 2 3 4 5 6 7 8 9

[edit] Perl 6

Translation of: Python
my @v = <9 8 7 6 5 0 1 2 3 4>;
say map { select(@v, $_) }, 1 .. 10;
 
sub partition(@vector, $left, $right, $pivot-index) {
my $pivot-value = @vector[$pivot-index];
@vector[$pivot-index, $right] = @vector[$right, $pivot-index];
my $store-index = $left;
for $left ..^ $right -> $i {
if @vector[$i] < $pivot-value {
@vector[$store-index, $i] = @vector[$i, $store-index];
$store-index++;
}
}
@vector[$right, $store-index] = @vector[$store-index, $right];
return $store-index;
}
 
sub select( @vector,
\k where 1 .. @vector,
\l where 0 .. @vector = 0,
\r where l .. @vector = @vector.end ) {
 
my ($k, $left, $right) = k, l, r;
 
loop {
my $pivot-index = ($left..$right).pick;
my $pivot-new-index = partition(@vector, $left, $right, $pivot-index);
my $pivot-dist = $pivot-new-index - $left + 1;
given $pivot-dist <=> $k {
when Same {
return @vector[$pivot-new-index];
}
when Decrease {
$right = $pivot-new-index - 1;
}
when Increase {
$k -= $pivot-dist;
$left = $pivot-new-index + 1;
}
}
}
}
Output:
0 1 2 3 4 5 6 7 8 9

[edit] PL/I

 
quick: procedure options (main); /* 4 April 2014 */
 
partition: procedure (list, left, right, pivot_Index) returns (fixed binary);
declare list (*) fixed binary;
declare (left, right, pivot_index) fixed binary;
declare (store_index, pivot_value) fixed binary;
declare I fixed binary;
 
pivot_Value = list(pivot_Index);
call swap (pivot_Index, right); /* Move pivot to end */
store_Index = left;
do i = left to right-1;
if list(i) < pivot_Value then
do;
call swap (store_Index, i);
store_Index = store_index + 1;
end;
end;
call swap (right, store_Index); /* Move pivot to its final place */
return (store_Index);
 
swap: procedure (i, j);
declare (i, j) fixed binary; declare t fixed binary;
 
t = list(i); list(i) = list(j); list(j) = t;
end swap;
end partition;
 
/* Returns the n-th smallest element of list within left..right inclusive */
/* (i.e. left <= n <= right). */
quick_select: procedure (list, left, right, n) recursive returns (fixed binary);
declare list(*) fixed binary;
declare (left, right, n) fixed binary;
declare pivot_index fixed binary;
 
if left = right then /* If the list contains only one element */
return ( list(left) ); /* Return that element */
pivot_Index = (left+right)/2;
/* select a pivot_Index between left and right, */
/* e.g. left + Math.floor(Math.random() * (right - left + 1)) */
pivot_Index = partition(list, left, right, pivot_Index);
/* The pivot is in its final sorted position. */
if n = pivot_Index then
return ( list(n) );
else if n < pivot_Index then
return ( quick_select(list, left, pivot_Index - 1, n) );
else
return ( quick_select(list, pivot_Index + 1, right, n) );
 
end quick_select;
 
declare a(10) fixed binary static initial (9, 8, 7, 6, 5, 0, 1, 2, 3, 4);
declare I fixed binary;
 
do i = 1 to 10;
put skip edit ('The ', trim(i), '-th element is ', quick_select((a), 1, 10, (i) )) (a);
end;
 
end quick;

Output:

The 1-th element is         0
The 2-th element is         1
The 3-th element is         2
The 4-th element is         3
The 5-th element is         4
The 6-th element is         5
The 7-th element is         6
The 8-th element is         7
The 9-th element is         8
The 10-th element is         9

[edit] Python

A direct implementation of the Wikipedia pseudo-code, using a random initial pivot. I added some input flexibility allowing sensible defaults for left and right function arguments.

import random
 
def partition(vector, left, right, pivotIndex):
pivotValue = vector[pivotIndex]
vector[pivotIndex], vector[right] = vector[right], vector[pivotIndex] # Move pivot to end
storeIndex = left
for i in range(left, right):
if vector[i] < pivotValue:
vector[storeIndex], vector[i] = vector[i], vector[storeIndex]
storeIndex += 1
vector[right], vector[storeIndex] = vector[storeIndex], vector[right] # Move pivot to its final place
return storeIndex
 
def _select(vector, left, right, k):
"Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive."
while True:
pivotIndex = random.randint(left, right) # select pivotIndex between left and right
pivotNewIndex = partition(vector, left, right, pivotIndex)
pivotDist = pivotNewIndex - left
if pivotDist == k:
return vector[pivotNewIndex]
elif k < pivotDist:
right = pivotNewIndex - 1
else:
k -= pivotDist + 1
left = pivotNewIndex + 1
 
def select(vector, k, left=None, right=None):
"""\
Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1].
left, right default to (0, len(vector) - 1) if omitted
"""

if left is None:
left = 0
lv1 = len(vector) - 1
if right is None:
right = lv1
assert vector and k >= 0, "Either null vector or k < 0 "
assert 0 <= left <= lv1, "left is out of range"
assert left <= right <= lv1, "right is out of range"
return _select(vector, left, right, k)
 
if __name__ == '__main__':
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print([select(v, i) for i in range(10)])
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] Racket

(define (quickselect A k)
(define pivot (list-ref A (random (length A))))
(define A1 (filter (curry > pivot) A))
(define A2 (filter (curry < pivot) A))
(cond
[(<= k (length A1)) (quickselect A1 k)]
[(> k (- (length A) (length A2))) (quickselect A2 (- k (- (length A) (length A2))))]
[else pivot]))
 
(define a '(9 8 7 6 5 0 1 2 3 4))
(display (string-join (map number->string (for/list ([k 10]) (quickselect a (+ 1 k)))) ", "))
 
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[edit] REXX

/*REXX program sorts a list (which may be numbers)  using  quick select.*/
parse arg list; if list='' then list=9 8 7 6 5 0 1 2 3 4 /*default?*/
do #=1 for words(list); @.#=word(list,#); end /*#*/; #=#-1
/* [↓] #=number of items in list*/
do j=1 for # /*show 1 ──► # place and value.*/
say ' item' right(j,length(#))", value: " qSel(1,#,j)
end /*j*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────QPART subroutine────────────────────*/
qPart: procedure expose @.; parse arg L 1 ?,R,pivotIndex;pVal=@.pivotIndex
parse value @.pivotIndex @.R with @.R @.pivotIndex /*swap 2 items*/
do k=L to R-1 /*process the left side of list. */
if @.k>pVal then iterate /*when item>pivotValue, skip it. */
parse value @.? @.k with @.k @.? /*swap 2 items*/
 ?=?+1 /*next item. */
end /*k*/
parse value @.R @.? with @.? @.R /*swap 2 items*/
return ?
/*──────────────────────────────────QSEL subroutine─────────────────────*/
qSel: procedure expose @.; parse arg L,R,z; if L==R then return @.L
do forever /*keep looping until all done. */
pivotNewIndex=qPart(L, R, (L+R)%2) /*partition the list into ≈ ½. */
pivotDist=pivotNewIndex-L+1
if pivotDist==z then return @.pivotNewIndex
else if z<pivotDist then R=pivotNewIndex-1
else do
z=z-pivotDist
L=pivotNewindex+1
end
end /*forever*/

output   when using the default input:

         item  1,  value:  0
         item  2,  value:  1
         item  3,  value:  2
         item  4,  value:  3
         item  5,  value:  4
         item  6,  value:  5
         item  7,  value:  6
         item  8,  value:  7
         item  9,  value:  8
         item 10,  value:  9

[edit] Ruby

def quickselect(a, k)
arr = a.dup # we will be modifying it
loop do
pivot = arr.delete_at(rand(arr.length))
left, right = arr.partition { |x| x < pivot }
if k == left.length
return pivot
elsif k < left.length
arr = left
else
k = k - left.length - 1
arr = right
end
end
end
 
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
p v.each_index.map { |i| quickselect(v, i) }
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] Scala

import scala.util.Random
 
object QuickSelect {
def quickSelect[A <% Ordered[A]](seq: Seq[A], n: Int, rand: Random = new Random): A = {
val pivot = rand.nextInt(seq.length);
val (left, right) = seq.partition(_ < seq(pivot))
if (left.length == n) {
seq(pivot)
} else if (left.length < n) {
quickSelect(right, n - left.length, rand)
} else {
quickSelect(left, n, rand)
}
}
 
def main(args: Array[String]): Unit = {
val v = Array(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
println((0 until v.length).map(quickSelect(v, _)).mkString(", "))
}
}
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[edit] Sidef

func quickselect(a, k) {
var pivot = a.pick;
var left = a.grep{|i| i < pivot};
var right = a.grep{|i| i > pivot};
 
switch(var l = left.len)
when(k) { pivot }
case(k < l) { __FUNC__(left, k) }
default { __FUNC__(right, k - l - 1) };
}
 
var v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
say v.range.map{|i| quickselect(v, i)}.dump;
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] Standard ML

fun quickselect (_, _, []) = raise Fail "empty"
| quickselect (k, cmp, x :: xs) = let
val (ys, zs) = List.partition (fn y => cmp (y, x) = LESS) xs
val l = length ys
in
if k < l then
quickselect (k, cmp, ys)
else if k > l then
quickselect (k-l-1, cmp, zs)
else
x
end

Usage:

- val v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
val v = [9,8,7,6,5,0,1,2,3,4] : int list
- List.tabulate (10, fn i => quickselect (i, Int.compare, v));   
val it = [0,1,2,3,4,5,6,7,8,9] : int list

[edit] Swift

func select<T where T : Comparable>(var elements: [T], n: Int) -> T {
var r = indices(elements)
while true {
let pivotIndex = partition(&elements, r)
if n == pivotIndex {
return elements[pivotIndex]
} else if n < pivotIndex {
r.endIndex = pivotIndex
} else {
r.startIndex = pivotIndex+1
}
}
}
 
for i in 0 ..< 10 {
let a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print(select(a, i))
if i < 9 { print(", ") }
}
println()
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[edit] Tcl

Translation of: Python
# Swap the values at two indices of a list
proc swap {list i j} {
upvar 1 $list l
set tmp [lindex $l $i]
lset l $i [lindex $l $j]
lset l $j $tmp
}
 
proc quickselect {vector k {left 0} {right ""}} {
set last [expr {[llength $vector] - 1}]
if {$right eq ""} {
set right $last
}
# Sanity assertions
if {![llength $vector] || $k <= 0} {
error "Either empty vector, or k <= 0"
} elseif {![tcl::mathop::<= 0 $left $last]} {
error "left is out of range"
} elseif {![tcl::mathop::<= $left $right $last]} {
error "right is out of range"
}
 
# the _select core, inlined
while 1 {
set pivotIndex [expr {int(rand()*($right-$left))+$left}]
 
# the partition core, inlined
set pivotValue [lindex $vector $pivotIndex]
swap vector $pivotIndex $right
set storeIndex $left
for {set i $left} {$i <= $right} {incr i} {
if {[lindex $vector $i] < $pivotValue} {
swap vector $storeIndex $i
incr storeIndex
}
}
swap vector $right $storeIndex
set pivotNewIndex $storeIndex
 
set pivotDist [expr {$pivotNewIndex - $left + 1}]
if {$pivotDist == $k} {
return [lindex $vector $pivotNewIndex]
} elseif {$k < $pivotDist} {
set right [expr {$pivotNewIndex - 1}]
} else {
set k [expr {$k - $pivotDist}]
set left [expr {$pivotNewIndex + 1}]
}
}
}

Demonstrating:

set v {9 8 7 6 5 0 1 2 3 4}
foreach i {1 2 3 4 5 6 7 8 9 10} {
puts "$i => [quickselect $v $i]"
}
Output:
1 => 0
2 => 1
3 => 2
4 => 3
5 => 4
6 => 5
7 => 6
8 => 7
9 => 8
10 => 9

[edit] zkl

Translation of: Wikipedia

This is the in place version rather than the much more concise copy-partition functional method. A copy of the input list is made to cover the case it is immutable (or the input shouldn't be changed)

fcn qselect(list,nth){	// in place quick select
fcn(list,left,right,nth){
if (left==right) return(list[left]);
pivotIndex:=(left+right)/2; // or median of first,middle,last
 
// partition
pivot:=list[pivotIndex];
list.swap(pivotIndex,right); // move pivot to end
pivotIndex := left;
i:=left; do(right-left){ // foreach i in ([left..right-1])
if (list[i] < pivot){
list.swap(i,pivotIndex);
pivotIndex += 1;
}
i += 1;
}
list.swap(pivotIndex,right); // move pivot to final place
 
if (nth==pivotIndex) return(list[nth]);
if (nth<pivotIndex) return(self.fcn(list,left,pivotIndex-1,nth));
return(self.fcn(list,pivotIndex+1,right,nth));
}(list.copy(),0,list.len()-1,nth);
}
list:=T(10, 9, 8, 7, 6, 1, 2, 3, 4, 5);
foreach nth in (list.len()){ println(nth,": ",qselect(list,nth)) }
Output:
0: 1
1: 2
2: 3
3: 4
4: 5
5: 6
6: 7
7: 8
8: 9
9: 10
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox