Quickselect algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
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.
11l
<lang 11l>F partition(&vector, left, right, pivotIndex)
V pivotValue = vector[pivotIndex]
swap(&vector[pivotIndex], &vector[right])
V storeIndex = left
L(i) left .< right
I vector[i] < pivotValue
swap(&vector[storeIndex], &vector[i])
storeIndex++
swap(&vector[right], &vector[storeIndex])
R storeIndex
F _select(&vector, =left, =right, =k)
‘Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive.’
L
V pivotIndex = (left + right) I/ 2
V pivotNewIndex = partition(&vector, left, right, pivotIndex)
V pivotDist = pivotNewIndex - left
I pivotDist == k
R vector[pivotNewIndex]
E I k < pivotDist
right = pivotNewIndex - 1
E
k -= pivotDist + 1
left = pivotNewIndex + 1
F select(&vector, k)
‘ 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 ’ V left = 0 V lv1 = vector.len - 1 V right = lv1 assert(!vector.empty & k >= 0, ‘Either null vector or k < 0 ’) assert(left C 0 .. lv1, ‘left is out of range’) assert(right C left .. lv1, ‘right is out of range’) R _select(&vector, left, right, k)
V v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] print((0.<10).map(i -> select(&:v, i)))</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Action!
<lang Action!>PROC Swap(BYTE ARRAY tab INT i,j)
BYTE tmp
tmp=tab(i) tab(i)=tab(j) tab(j)=tmp
RETURN
BYTE FUNC QuickSelect(BYTE ARRAY tab INT count,index)
INT px,i,j,k BYTE pv
DO
px=count/2
pv=tab(px)
Swap(tab,px,count-1)
i=0
FOR j=0 TO count-2
DO
IF tab(j)<pv THEN
Swap(tab,i,j)
i==+1
FI
OD
IF i=index THEN
RETURN (pv)
ELSEIF i>index THEN
;left part of tab from 0 to i-1
count=i
ELSE
Swap(tab,i,count-1)
;right part of tab from i+1 to count-1
tab==+(i+1)
count==-(i+1)
index==-(i+1)
FI
OD
RETURN (0)
PROC Main()
DEFINE COUNT="10" BYTE ARRAY data=[9 8 7 6 5 0 1 2 3 4],tab(COUNT) BYTE i,res
FOR i=0 TO COUNT-1 DO MoveBlock(tab,data,COUNT) res=QuickSelect(tab,COUNT,i) PrintB(res) Put(32) OD
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
0 1 2 3 4 5 6 7 8 9
ALGOL 68
<lang algol68>BEGIN
# returns the kth lowest element of list using the quick select algorithm #
PRIO QSELECT = 1;
OP QSELECT = ( INT k, REF[]INT list )INT:
IF LWB list > UPB list THEN
# empty list #
0
ELSE
# non-empty list #
# partitions the subset of list from left to right #
PROC partition = ( REF[]INT list, INT left, right, pivot index )INT:
BEGIN
# swaps elements a and b in list #
PROC swap = ( REF[]INT list, INT a, b )VOID:
BEGIN
INT t = list[ a ];
list[ a ] := list[ b ];
list[ b ] := t
END # swap # ;
INT pivot value = list[ pivot index ];
swap( list, pivot index, right );
INT store index := left;
FOR i FROM left TO right - 1 DO
IF list[ i ] < pivot value THEN
swap( list, store index, i );
store index +:= 1
FI
OD;
swap( list, right, store index );
store index
END # partition # ;
INT left := LWB list, right := UPB list, result := 0;
BOOL found := FALSE;
WHILE NOT found DO
IF left = right THEN
result := list[ left ];
found := TRUE
ELSE
INT pivot index = partition( list, left, right, left + ENTIER ( ( random * ( right - left ) + 1 ) ) );
IF k = pivot index THEN
result := list[ k ];
found := TRUE
ELIF k < pivot index THEN
right := pivot index - 1
ELSE
left := pivot index + 1
FI
FI
OD;
result
FI # QSELECT # ;
# test cases #
FOR i TO 10 DO
[ 1 : 10 ]INT test := []INT( 9, 8, 7, 6, 5, 0, 1, 2, 3, 4 );
print( ( whole( i, -2 ), ": ", whole( i QSELECT test, -3 ), newline ) )
OD
END</lang>
- Output:
1: 0 2: 1 3: 2 4: 3 5: 4 6: 5 7: 6 8: 7 9: 8 10: 9
AppleScript
Procedural
<lang applescript>on quickselect(theList, l, r, k)
script o
property lst : theList's items -- Shallow copy.
end script
repeat
-- Median-of-3 pivot selection.
set leftValue to item l of o's lst
set rightValue to item r of o's lst
set pivot to item ((l + r) div 2) of o's lst
set leftGreaterThanRight to (leftValue > rightValue)
if (leftValue > pivot) then
if (leftGreaterThanRight) then
if (rightValue > pivot) then set pivot to rightValue
else
set pivot to leftValue
end if
else if (pivot > rightValue) then
if (leftGreaterThanRight) then
set pivot to leftValue
else
set pivot to rightValue
end if
end if
-- Initialise pivot store indices and swap the already compared outer values here if necessary.
set pLeft to l - 1
set pRight to r + 1
if (leftGreaterThanRight) then
set item r of o's lst to leftValue
set item l of o's lst to rightValue
if (leftValue = pivot) then
set pRight to r
else if (rightValue = pivot) then
set pLeft to l
end if
else
if (leftValue = pivot) then set pLeft to l
if (rightValue = pivot) then set pRight to r
end if
-- Continue three-way partitioning.
set i to l + 1
set j to r - 1
repeat until (i > j)
set leftValue to item i of o's lst
repeat while (leftValue < pivot)
set i to i + 1
set leftValue to item i of o's lst
end repeat
set rightValue to item j of o's lst
repeat while (rightValue > pivot)
set j to j - 1
set rightValue to item j of o's lst
end repeat
if (j > i) then
if (leftValue = pivot) then
set pRight to pRight - 1
if (pRight > j) then
set leftValue to item pRight of o's lst
set item pRight of o's lst to pivot
end if
end if
if (rightValue = pivot) then
set pLeft to pLeft + 1
if (pLeft < i) then
set rightValue to item pLeft of o's lst
set item pLeft of o's lst to pivot
end if
end if
set item j of o's lst to leftValue
set item i of o's lst to rightValue
else if (i > j) then
exit repeat
end if
set i to i + 1
set j to j - 1
end repeat
-- Swap stored pivot(s) into a central partition.
repeat with p from l to pLeft
if (j > pLeft) then
set item p of o's lst to item j of o's lst
set item j of o's lst to pivot
set j to j - 1
else
set j to p - 1
exit repeat
end if
end repeat
repeat with p from r to pRight by -1
if (i < pRight) then
set item p of o's lst to item i of o's lst
set item i of o's lst to pivot
set i to i + 1
else
set i to p + 1
exit repeat
end if
end repeat
-- If k's in either of the outer partitions, repeat for that partition. Othewise return the item in slot k.
if (k ≥ i) then
set l to i
else if (k ≤ j) then
set r to j
else
return item k of o's lst
end if
end repeat
end quickselect
-- Task code: set theVector to {9, 8, 7, 6, 5, 0, 1, 2, 3, 4} set selected to {} set vectorLength to (count theVector) repeat with i from 1 to vectorLength
set end of selected to quickselect(theVector, 1, vectorLength, i)
end repeat return selected</lang>
- Output:
<lang applescript>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}</lang>
Functional
<lang applescript>----------------------- QUICKSELECT ------------------------
-- quickSelect :: Ord a => [a] -> Int -> a on quickSelect(xxs)
script
on |λ|(k)
script go
on |λ|(xxs, k)
set {x, xs} to {item 1 of xxs, rest of xxs}
set {ys, zs} to partition(gt(x), xs)
set lng to length of ys
if k < lng then
|λ|(ys, k)
else
if k > lng then
|λ|(zs, k - lng - 1)
else
x
end if
end if
end |λ|
end script
if 0 ≤ k and k < length of xxs then
tell go to |λ|(xxs, k)
else
missing value
end if
end |λ|
end script
end quickSelect
TEST ---------------------------
on run
set xs to {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
map(quickSelect(xs), enumFromTo(0, (length of xs) - 1))
end run
GENERAL AND REUSABLE PURE FUNCTIONS ------------
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- gt :: Ord a => a -> a -> Bool
on gt(x)
script
on |λ|(y)
x > y
end |λ|
end script
end gt
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- partition :: (a -> Bool) -> [a] -> ([a], [a])
on partition(p, xs)
tell mReturn(p)
set {ys, zs} to {{}, {}}
repeat with x in xs
set v to contents of x
if |λ|(v) then
set end of ys to v
else
set end of zs to v
end if
end repeat
end tell
{ys, zs}
end partition</lang>
- Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Arturo
<lang rebol>quickselect: function [a k][
arr: new a
while ø [
indx: random 0 (size arr)-1
pivot: arr\[indx]
remove 'arr .index indx
left: select arr 'item -> item<pivot
right: select arr 'item -> item>pivot
case [k]
when? [= size left]-> return pivot
when? [< size left]-> arr: new left
else [
k: (k - size left) - 1
arr: new right
]
]
]
v: [9 8 7 6 5 0 1 2 3 4]
print map 0..(size v)-1 'i ->
quickselect v i</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
AutoHotkey
(AutoHotkey1.1+)
A direct implementation of the Wikipedia pseudo-code. <lang AutoHotkey>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 }</lang> Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
C
<lang 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; }</lang>
- Output:
0: 0 1: 1 2: 2 3: 3 4: 4 5: 5 6: 6 7: 7 8: 8 9: 9
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.
<lang csharp>// ---------------------------------------------------------------------------------------------- // // 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 }
}</lang>
- 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 >
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.
<lang cpp>#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;
}</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
- Implementation
A more explicit implementation: <lang cpp>#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;
}</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
CLU
<lang clu>quick = cluster [T: type] is select
where T has lt: proctype (T,T) returns (bool)
aT = array[T]
sT = sequence[T]
rep = null
swap = proc (list: aT, a, b: int)
temp: T := list[a]
list[a] := list[b]
list[b] := temp
end swap
partition = proc (list: aT, left, right, pivotIndex: int) returns (int)
pivotValue: T := list[pivotIndex]
swap(list, pivotIndex, right)
storeIndex: int := left
for i: int in int$from_to(left, right-1) do
if list[i] < pivotValue then
swap(list, storeIndex, i)
storeIndex := storeIndex + 1
end
end
swap(list, right, storeIndex)
return(storeIndex)
end partition
_select = proc (list: aT, left, right, k: int) returns (T)
if left = right then
return(list[left])
end
pivotIndex: int := left + (right - left + 1) / 2
pivotIndex := partition(list, left, right, pivotIndex)
if k = pivotIndex then
return(list[k])
elseif k < pivotIndex then
return(_select(list, left, pivotIndex-1, k))
else
return(_select(list, pivotIndex + 1, right, k))
end
end _select
select = proc (list: sT, k: int) returns (T)
return(_select(sT$s2a(list), 1, sT$size(list), k))
end select
end quick
start_up = proc ()
po: stream := stream$primary_output()
vec: sequence[int] := sequence[int]$[9,8,7,6,5,0,1,2,3,4]
for k: int in int$from_to(1, 10) do
item: int := quick[int]$select(vec, k)
stream$putl(po, int$unparse(k) || ": " || int$unparse(item))
end
end start_up</lang>
- Output:
1: 0 2: 1 3: 2 4: 3 5: 4 6: 5 7: 6 8: 7 9: 8 10: 9
COBOL
The following is in the Managed COBOL dialect:
<lang 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.</lang>
Common Lisp
<lang lisp> (defun quickselect (n _list)
(let* ((ys (remove-if (lambda (x) (< (car _list) x)) (cdr _list)))
(zs (remove-if-not (lambda (x) (< (car _list) x)) (cdr _list)))
(l (length ys))
)
(cond ((< n l) (quickselect n ys))
((> n l) (quickselect (- n l 1) zs))
(t (car _list)))
)
)
(defparameter a '(9 8 7 6 5 0 1 2 3 4)) (format t "~a~&" (mapcar (lambda (x) (quickselect x a)) (loop for i from 0 below (length a) collect i))) </lang>
- Output:
(0 1 2 3 4 5 6 7 8 9)
Crystal
<lang ruby>def quickselect(a, k)
arr = a.dup # we will be modifying it
loop do
pivot = arr.delete_at(rand(arr.size))
left, right = arr.partition { |x| x < pivot }
if k == left.size
return pivot
elsif k < left.size
arr = left
else
k = k - left.size - 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) }.to_a </lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
D
Standard Version
This could use a different algorithm: <lang d>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], " ");
}
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
Array Version
<lang d>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;
}</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Delphi
<lang Delphi> program Quickselect_algorithm;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
function quickselect(list: TArray<Integer>; k: Integer): Integer;
procedure Swap(i, j: Integer); var tmp: Integer; begin tmp := list[i]; list[i] := list[j]; list[j] := tmp; end;
begin
repeat var px := length(list) div 2; var pv := list[px]; var last := length(list) - 1;
Swap(px, last);
var i := 0;
for var j := 0 to last - 1 do
if list[j] < pv then
begin
swap(i, j);
inc(i);
end;
if i = k then
exit(pv);
if k < i then
delete(list, i, length(list))
else
begin
Swap(i, last);
delete(list, 0, i + 1);
dec(k, i + 1);
end;
until false;
end;
begin
var i := 0;
while True do
begin
var v: TArray<Integer> := [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
if i = length(v) then
Break;
Writeln(quickselect(v, i));
inc(i);
end;
Readln;
end.</lang>
EasyLang
<lang>func qselect k d[] . res .
#
subr partition
mid = left
for i = left + 1 to right
if d[i] < d[left]
mid += 1
swap d[i] d[mid]
.
.
swap d[left] d[mid]
.
right = len d[] - 1
repeat
call partition
until mid = k
if mid < k
left = mid + 1
else
right = mid - 1
.
.
res = d[k]
. d[] = [ 9 8 7 6 5 0 1 2 3 4 ] for i range len d[]
call qselect i d[] r print r
. </lang>
Elixir
<lang elixir>defmodule Quick do
def select(k, [x|xs]) do
{ys, zs} = Enum.partition(xs, fn e -> e < x end)
l = length(ys)
cond do
k < l -> select(k, ys)
k > l -> select(k - l - 1, zs)
true -> x
end
end
def test do
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
Enum.map(0..length(v)-1, fn i -> select(i,v) end)
|> IO.inspect
end
end
Quick.test</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Erlang
<lang erlang> -module(quickselect).
-export([test/0]).
test() ->
V = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4],
lists:map(
fun(I) -> quickselect(I,V) end,
lists:seq(0, length(V) - 1)
).
quickselect(K, [X | Xs]) ->
{Ys, Zs} =
lists:partition(fun(E) -> E < X end, Xs),
L = length(Ys),
if
K < L ->
quickselect(K, Ys);
K > L ->
quickselect(K - L - 1, Zs);
true ->
X
end.
</lang>
Output:
[0,1,2,3,4,5,6,7,8,9]
F#
<lang fsharp> 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
</lang>
- Output:
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
Factor
<lang factor>USING: combinators kernel make math locals prettyprint sequences ; IN: rosetta-code.quickselect
- quickselect ( k seq -- n )
seq unclip :> ( xs x )
xs [ x < ] partition :> ( ys zs )
ys length :> l
{
{ [ k l < ] [ k ys quickselect ] }
{ [ k l > ] [ k l - 1 - zs quickselect ] }
[ x ]
} cond ;
- quickselect-demo ( -- )
{ 9 8 7 6 5 0 1 2 3 4 } dup length <iota> swap
[ [ quickselect , ] curry each ] { } make . ;
MAIN: quickselect-demo</lang>
- Output:
{ 0 1 2 3 4 5 6 7 8 9 }
Fortran
Conveniently, a function was already to hand for floating-point numbers and changing the type was trivial - because the array and its associates were declared in the same statement to facilitate exactly that. The style is F77 (except for the A(1:N) usage in the DATA statement, and the END FUNCTION usage) and it did not seem worthwhile activating the MODULE protocol of F90 just to save the tedium of having to declare INTEGER FINDELEMENT in the calling routine - doing so would require four additional lines... On the other hand, a MODULE would enable the convenient development of a collection of near-clones, one for each type of array (INTEGER, REAL*4, REAL*8) which could then be collected via an INTERFACE statement into forming an apparently generic function so that one needn't have to remember FINDELEMENTI2, FINDELEMENTI4, FINDELEMENTF4, FINDELEMENTF8, and so on. With multiple parameters of various types, the combinations soon become tiresomely numerous.
Those of a delicate disposition may wish to avert their eyes from the three-way IF-statement... <lang Fortran> INTEGER FUNCTION FINDELEMENT(K,A,N) !I know I can. Chase an order statistic: FindElement(N/2,A,N) leads to the median, with some odd/even caution. Careful! The array is shuffled: for i < K, A(i) <= A(K); for i > K, A(i) >= A(K). Charles Anthony Richard Hoare devised this method, as related to his famous QuickSort.
INTEGER K,N !Find the K'th element in order of an array of N elements, not necessarily in order.
INTEGER A(N),HOPE,PESTY !The array, and like associates.
INTEGER L,R,L2,R2 !Fingers.
L = 1 !Here we go.
R = N !The bounds of the work area within which the K'th element lurks.
DO WHILE (L .LT. R) !So, keep going until it is clamped.
HOPE = A(K) !If array A is sorted, this will be rewarded.
L2 = L !But it probably isn't sorted.
R2 = R !So prepare a scan.
DO WHILE (L2 .LE. R2) !Keep squeezing until the inner teeth meet.
DO WHILE (A(L2) .LT. HOPE) !Pass elements less than HOPE.
L2 = L2 + 1 !Note that at least element A(K) equals HOPE.
END DO !Raising the lower jaw.
DO WHILE (HOPE .LT. A(R2)) !Elements higher than HOPE
R2 = R2 - 1 !Are in the desired place.
END DO !And so we speed past them.
IF (L2 - R2) 1,2,3 !How have the teeth paused?
1 PESTY = A(L2) !On grit. A(L2) > HOPE and A(R2) < HOPE.
A(L2) = A(R2) !So swap the two troublemakers.
A(R2) = PESTY !To be as if they had been in the desired order all along.
2 L2 = L2 + 1 !Advance my teeth.
R2 = R2 - 1 !As if they hadn't paused on this pest.
3 END DO !And resume the squeeze, hopefully closing in K.
IF (R2 .LT. K) L = L2 !The end point gives the order position of value HOPE.
IF (K .LT. L2) R = R2 !But we want the value of order position K.
END DO !Have my teeth met yet?
FINDELEMENT = A(K) !Yes. A(K) now has the K'th element in order.
END FUNCTION FINDELEMENT !Remember! Array A has likely had some elements moved!
PROGRAM POKE
INTEGER FINDELEMENT !Not the default type for F.
INTEGER N !The number of elements.
PARAMETER (N = 10) !Fixed for the test problem.
INTEGER A(66) !An array of integers.
DATA A(1:N)/9, 8, 7, 6, 5, 0, 1, 2, 3, 4/ !The specified values.
WRITE (6,1) A(1:N) !Announce, and add a heading.
1 FORMAT ("Selection of the i'th element in order from an array.",/
1 "The array need not be in order, and may be reordered.",/
2 " i Val:Array elements...",/,8X,666I2)
DO I = 1,N !One by one,
WRITE (6,2) I,FINDELEMENT(I,A,N),A(1:N) !Request the i'th element.
2 FORMAT (I3,I4,":",666I2) !Match FORMAT 1.
END DO !On to the next trial.
END !That was easy.</lang>
To demonstrate that the array, if unsorted, will likely have elements re-positioned, the array's state after each call is shown.
Selection of the i'th element in order from an array.
The array need not be in order, and may be reordered.
i Val:Array elements...
9 8 7 6 5 0 1 2 3 4
1 0: 0 2 1 3 5 6 7 8 4 9
2 1: 0 1 2 3 5 6 7 8 4 9
3 2: 0 1 2 3 5 6 7 8 4 9
4 3: 0 1 2 3 5 6 7 8 4 9
5 4: 0 1 2 3 4 6 7 8 5 9
6 5: 0 1 2 3 4 5 7 8 6 9
7 6: 0 1 2 3 4 5 6 8 7 9
8 7: 0 1 2 3 4 5 6 7 8 9
9 8: 0 1 2 3 4 5 6 7 8 9
10 9: 0 1 2 3 4 5 6 7 8 9
Given an intention to make many calls on FINDELEMENT for the same array, the array might as well be fully sorted first by a routine specialising in that. Otherwise, if say going for quartiles, it would be better to start with the median and work out so as to have a better chance of avoiding unfortunate "pivot" values.
FreeBASIC
Una implementación directa del pseudocódigo de Wikipedia. <lang freebasic> Dim Shared As Long array(9), pivote
Function QuickPartition (array() As Long, izda As Long, dcha As Long, pivote As Long) As Long
Dim As Long pivotValue = array(pivote)
Swap array(pivote), array(dcha)
Dim As Long indice = izda
For i As Long = izda To dcha-1
If array(i) < pivotValue Then
Swap array(indice), array(i)
indice += 1
End If
Next i
Swap array(dcha), array(indice)
Return indice
End Function
Function QuickSelect(array() As Long, izda As Long, dcha As Long, k As Long) As Long
Do
If izda = dcha Then Return array(izda) : End If
pivote = izda
pivote = QuickPartition(array(), izda, dcha, pivote)
Select Case k
Case pivote
Return array(k)
Case Is < pivote
dcha = pivote - 1
Case Is > pivote
izda = pivote + 1
End Select
Loop
End Function
Dim As Long a = Lbound(array), b = Ubound(array) Print "Array desordenado: "; For i As Long = a To b
Read array(i) Print array(i);
Next i Data 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
Print !"\n\n Array ordenado: "; For i As Long = a To b
Print QuickSelect(array(), a, b, i);
Next i Sleep </lang>
- Output:
Array desordenado: 9 8 7 6 5 0 1 2 3 4 Array ordenado: 0 1 2 3 4 5 6 7 8 9
Go
<lang 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))
}
}</lang>
- 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:
<lang go>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)])
}
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
Haskell
<lang haskell>import Data.List (partition)
quickselect
:: Ord a => [a] -> Int -> a
quickselect (x:xs) k
| k < l = quickselect ys k | k > l = quickselect zs (k - l - 1) | otherwise = x where (ys, zs) = partition (< x) xs l = length ys
main :: IO () main =
print
((fmap . quickselect) <*> zipWith const [0 ..] $
[9, 8, 7, 6, 5, 0, 1, 2, 3, 4])</lang>
- Output:
[0,1,2,3,4,5,6,7,8,9]
Icon and Unicon
The following works in both languages. <lang unicon>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</lang>
Sample run:
->qs 9 8 7 6 5 0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 ->
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:
<lang J>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.
)</lang>
"Proof" that it works:
<lang J> 8 quickselect 9, 8, 7, 6, 5, 0, 1, 2, 3, 4 8</lang>
And, the required task example:
<lang J> ((10 {./:~) quickselect"0 1 ]) 9, 8, 7, 6, 5, 0, 1, 2, 3, 4 0 1 2 3 4 5 6 7 8 9</lang>
(Insert here: puns involving greater transparency, the emperor's new clothes, burlesque and maybe the dance of the seven veils.)
Java
<lang 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(); }
}</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
JavaScript
ES5
<lang javascript>// this just helps make partition read better function swap(items, firstIndex, secondIndex) {
var temp = items[firstIndex]; items[firstIndex] = items[secondIndex]; items[secondIndex] = temp;
};
// many algorithms on this page violate // the constraint that partition operates in place function partition(array, from, to) {
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random var pivotIndex = getRandomInt(from, to), pivot = array[pivotIndex]; swap(array, pivotIndex, to); pivotIndex = from;
for(var i = from; i <= to; i++) {
if(array[i] < pivot) {
swap(array, pivotIndex, i);
pivotIndex++;
}
};
swap(array, pivotIndex, to);
return pivotIndex;
};
// later versions of JS have TCO so this is safe function quickselectRecursive(array, from, to, statistic) {
if(array.length === 0 || statistic > array.length - 1) {
return undefined;
};
var pivotIndex = partition(array, from, to);
if(pivotIndex === statistic) {
return array[pivotIndex];
} else if(pivotIndex < statistic) {
return quickselectRecursive(array, pivotIndex, to, statistic);
} else if(pivotIndex > statistic) {
return quickselectRecursive(array, from, pivotIndex, statistic);
}
};
function quickselectIterative(array, k) {
if(array.length === 0 || k > array.length - 1) {
return undefined;
};
var from = 0, to = array.length,
pivotIndex = partition(array, from, to);
while(pivotIndex !== k) {
pivotIndex = partition(array, from, to);
if(pivotIndex < k) {
from = pivotIndex;
} else if(pivotIndex > k) {
to = pivotIndex;
}
};
return array[pivotIndex];
};
KthElement = {
find: function(array, element) {
var k = element - 1;
return quickselectRecursive(array, 0, array.length, k);
// you can also try out the Iterative version
// return quickselectIterative(array, k);
}
}</lang>
Example: <lang Javascript> var array = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4],
ks = Array.apply(null, {length: 10}).map(Number.call, Number);
ks.map(k => { KthElement.find(array, k) });</lang>
- Output:
<lang JavaScript>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];</lang>
ES6
<lang JavaScript>(() => {
'use strict';
// QUICKSELECT ------------------------------------------------------------
// quickselect :: Ord a => Int -> [a] -> a
const quickSelect = (k, xxs) => {
const
[x, xs] = uncons(xxs),
[ys, zs] = partition(v => v < x, xs),
l = length(ys);
return (k < l) ? (
quickSelect(k, ys)
) : (k > l) ? (
quickSelect(k - l - 1, zs)
) : x;
};
// GENERIC FUNCTIONS ------------------------------------------------------
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// length :: [a] -> Int const length = xs => xs.length;
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// partition :: Predicate -> List -> (Matches, nonMatches)
// partition :: (a -> Bool) -> [a] -> ([a], [a])
const partition = (p, xs) =>
xs.reduce((a, x) =>
p(x) ? [a[0].concat(x), a[1]] : [a[0], a[1].concat(x)], [
[],
[]
]);
// uncons :: [a] -> Maybe (a, [a]) const uncons = xs => xs.length ? [xs[0], xs.slice(1)] : undefined;
// TEST ------------------------------------------------------------------- const v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
return map(i => quickSelect(i, v), enumFromTo(0, length(v) - 1));
})();</lang>
- Output:
<lang JavaScript>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>
jq
<lang jq># 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;</lang>
Example: Notice that values of k that are too large or too small generate nothing. <lang jq>(0, 12, range(1;11)) as $k
| [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] | quickselect($k) | "k=\($k) => \(.)"</lang>
- Output:
<lang sh>$ 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 $</lang>
Julia
Using builtin function select:
<lang julia>v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
@show v select(v, 1:10)
</lang>
- Output:
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] select(v, 1:10) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Kotlin
<lang scala>// version 1.1.2
const val MAX = Int.MAX_VALUE val rand = java.util.Random()
fun partition(list:IntArray, left: Int, right:Int, pivotIndex: Int): Int {
val pivotValue = list[pivotIndex]
list[pivotIndex] = list[right]
list[right] = pivotValue
var storeIndex = left
for (i in left until right) {
if (list[i] < pivotValue) {
val tmp = list[storeIndex]
list[storeIndex] = list[i]
list[i] = tmp
storeIndex++
}
}
val temp = list[right]
list[right] = list[storeIndex]
list[storeIndex] = temp
return storeIndex
}
tailrec fun quickSelect(list: IntArray, left: Int, right: Int, k: Int): Int {
if (left == right) return list[left]
var pivotIndex = left + Math.floor((rand.nextInt(MAX) % (right - left + 1)).toDouble()).toInt()
pivotIndex = partition(list, left, right, pivotIndex)
if (k == pivotIndex)
return list[k]
else if (k < pivotIndex)
return quickSelect(list, left, pivotIndex - 1, k)
else
return quickSelect(list, pivotIndex + 1, right, k)
}
fun main(args: Array<String>) {
val list = intArrayOf(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
val right = list.size - 1
for (k in 0..9) {
print(quickSelect(list, 0, right, k))
if (k < 9) print(", ")
}
println()
}</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Lua
<lang Lua>function partition (list, left, right, pivotIndex)
local pivotValue = list[pivotIndex]
list[pivotIndex], list[right] = list[right], list[pivotIndex]
local storeIndex = left
for i = left, right do
if list[i] < pivotValue then
list[storeIndex], list[i] = list[i], list[storeIndex]
storeIndex = storeIndex + 1
end
end
list[right], list[storeIndex] = list[storeIndex], list[right]
return storeIndex
end
function quickSelect (list, left, right, n)
local pivotIndex
while 1 do
if left == right then return list[left] end
pivotIndex = math.random(left, right)
pivotIndex = partition(list, left, right, pivotIndex)
if n == pivotIndex then
return list[n]
elseif n < pivotIndex then
right = pivotIndex - 1
else
left = pivotIndex + 1
end
end
end
math.randomseed(os.time()) local vec = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4} for i = 1, 10 do print(i, quickSelect(vec, 1, #vec, i) .. " ") end</lang>
- Output:
1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9
Maple
<lang Maple>part := proc(arr, left, right, pivot) local val,safe,i: val := arr[pivot]: arr[pivot], arr[right] := arr[right], arr[pivot]: safe := left: for i from left to right do if arr[i] < val then arr[safe], arr[i] := arr[i], arr[safe]: safe := safe + 1: end if: end do: arr[right], arr[safe] := arr[safe], arr[right]: return safe: end proc:
quickselect := proc(arr,k) local pivot,left,right: left,right := 1,numelems(arr): while(true)do if left = right then return arr[left]: end if: pivot := trunc((left+right)/2); pivot := part(arr, left, right, pivot): if k = pivot then return arr[k]: elif k < pivot then right := pivot-1: else left := pivot+1: end if: end do: end proc: roll := rand(1..20): demo := Array([seq(roll(), i=1..20)]); map(x->printf("%d ", x), demo): print(quickselect(demo,7)): print(quickselect(demo,14)):</lang>
- Example:
5 4 2 1 3 6 8 11 11 11 8 11 9 11 16 20 20 18 17 16 8 11
Mathematica / Wolfram Language
<lang Mathematica>Quickselect[ds : DataStructure["DynamicArray", _], k_] := QuickselectWorker[ds, 1, ds["Length"], k]; QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0},
While[True,
If[low === high,
Return[ds["Part", low]]
];
pivotIdx = SelectPartition[ds, low, high];
Which[k === pivotIdx,
Return[ds["Part", k]],
k < pivotIdx,
high = pivotIdx - 1,
True,
low = pivotIdx + 1
]
]
];
SelectPartition[ds_, low_, high_] := Module[{pivot = ds["Part", high], i = low, j},
Do[
If[ds["Part", j] <= pivot,
ds["SwapPart", i, j];
i = i + 1
]
,
{j, low, high - 1}
];
ds["SwapPart", i, high];
i
];
ds = CreateDataStructure["DynamicArray", {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}]; Quickselect[ds, #] & /@ Range[10]</lang>
- Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Mercury
<lang Mercury>%%%-------------------------------------------------------------------
- - module quickselect_task.
- - interface.
- - import_module io.
- - pred main(io, io).
- - mode main(di, uo) is det.
- - implementation.
- - import_module array.
- - import_module exception.
- - import_module int.
- - import_module list.
- - import_module random.
- - import_module random.sfc64.
- - import_module string.
%%%------------------------------------------------------------------- %%% %%% Partitioning a subarray into two halves: one with elements less %%% than or equal to a pivot, the other with elements greater than or %%% equal to a pivot. %%% %%% The implementation is tail-recursive. %%%
- - pred partition(pred(T, T), T, int, int, array(T), array(T), int).
- - mode partition(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition(Less_than, Pivot, I_first, I_last, Arr0, Arr, I_pivot) :-
I = I_first - 1, J = I_last + 1, partition_loop(Less_than, Pivot, I, J, Arr0, Arr, I_pivot).
- - pred partition_loop(pred(T, T), T, int, int,
array(T), array(T), int).
- - mode partition_loop(pred(in, in) is semidet, in, in, in,
array_di, array_uo, out).
partition_loop(Less_than, Pivot, I, J, Arr0, Arr, Pivot_index) :-
if (I = J) then (Arr = Arr0,
Pivot_index = I)
else (I1 = I + 1,
I2 = search_right(Less_than, Pivot, I1, J, Arr0),
(if (I2 = J) then (Arr = Arr0,
Pivot_index = J)
else (J1 = J - 1,
J2 = search_left(Less_than, Pivot, I2, J1, Arr0),
swap(I2, J2, Arr0, Arr1),
partition_loop(Less_than, Pivot, I2, J2, Arr1, Arr,
Pivot_index)))).
- - func search_right(pred(T, T), T, int, int, array(T)) = int.
- - mode search_right(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_right(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (I = K) else if Less_than(Pivot, Arr0^elem(I)) then (I = K) else (search_right(Less_than, Pivot, I + 1, J, Arr0) = K).
- - func search_left(pred(T, T), T, int, int, array(T)) = int.
- - mode search_left(pred(in, in) is semidet,
in, in, in, in) = out is det.
search_left(Less_than, Pivot, I, J, Arr0) = K :-
if (I = J) then (J = K) else if Less_than(Arr0^elem(J), Pivot) then (J = K) else (search_left(Less_than, Pivot, I, J - 1, Arr0) = K).
%%%------------------------------------------------------------------- %%% %%% Quickselect with a random pivot. %%% %%% The implementation is tail-recursive. One has to pass the routine %%% a random number generator of type M, attached to the IO state. %%% %%% I use a random pivot to get O(n) worst case *expected* running %%% time. Code using a random pivot is easy to write and read, and for %%% most purposes comes close enough to a criterion set by Scheme's %%% SRFI-132: "Runs in O(n) time." (See %%% https://srfi.schemers.org/srfi-132/srfi-132.html) %%% %%% Of course we are not bound here by SRFI-132, but still I respect %%% it as a guide. %%% %%% A "median of medians" pivot gives O(n) running time, but is more %%% complicated. (That is, of course, assuming you are not writing %%% your own random number generator and making it a complicated one.) %%%
%% quickselect/8 selects the (K+1)th largest element of Arr.
- - pred quickselect(pred(T, T)::pred(in, in) is semidet, int::in,
array(T)::array_di, array(T)::array_uo,
T::out, M::in, io::di, io::uo)
is det <= urandom(M, io).
quickselect(Less_than, K, Arr0, Arr, Elem, M, !IO) :-
bounds(Arr0, I_first, I_last), quickselect(Less_than, I_first, I_last, K, Arr0, Arr, Elem, M, !IO).
%% quickselect/10 selects the (K+1)th largest element of %% Arr[I_first..I_last].
- - pred quickselect(pred(T, T)::pred(in, in) is semidet,
int::in, int::in, int::in,
array(T)::array_di, array(T)::array_uo,
T::out, M::in, io::di, io::uo)
is det <= urandom(M, io).
quickselect(Less_than, I_first, I_last, K, Arr0, Arr, Elem, M, !IO) :-
if (0 =< K, K =< I_last - I_first)
then (K_adjusted_for_range = K + I_first,
quickselect_loop(Less_than, I_first, I_last,
K_adjusted_for_range,
Arr0, Arr, Elem, M, !IO))
else throw("out of range").
- - pred quickselect_loop(pred(T, T)::pred(in, in) is semidet,
int::in, int::in, int::in,
array(T)::array_di, array(T)::array_uo,
T::out, M::in, io::di, io::uo)
is det <= urandom(M, io).
quickselect_loop(Less_than, I_first, I_last, K,
Arr0, Arr, Elem, M, !IO) :-
if (I_first = I_last) then (Arr = Arr0,
Elem = Arr0^elem(I_first))
else (uniform_int_in_range(M, I_first, I_last - I_first + 1,
I_pivot, !IO),
Pivot = Arr0^elem(I_pivot),
%% Move the last element to where the pivot had been. Perhaps
%% the pivot was already the last element, of course. In any
%% case, we shall partition only from I_first to I_last - 1.
Elem_last = Arr0^elem(I_last),
Arr1 = (Arr0^elem(I_pivot) := Elem_last),
%% Partition the array in the range I_first..I_last - 1,
%% leaving out the last element (which now can be considered
%% garbage).
partition(Less_than, Pivot, I_first, I_last - 1, Arr1, Arr2,
I_final),
%% Now everything that is less than the pivot is to the left
%% of I_final.
%% Put the pivot at I_final, moving the element that had been
%% there to the end. If I_final = I_last, then this element is
%% actually garbage and will be overwritten with the pivot,
%% which turns out to be the greatest element. Otherwise, the
%% moved element is not less than the pivot and so the
%% partitioning is preserved.
Elem_to_move = Arr2^elem(I_final),
Arr3 = (Arr2^elem(I_last) := Elem_to_move),
Arr4 = (Arr3^elem(I_final) := Pivot),
%% Compare I_final and K, to see what to do next.
(if (I_final < K)
then quickselect_loop(Less_than, I_final + 1, I_last, K,
Arr4, Arr, Elem, M, !IO)
else if (K < I_final)
then quickselect_loop(Less_than, I_first, I_final - 1, K,
Arr4, Arr, Elem, M, !IO)
else (Arr = Arr4,
Elem = Arr4^elem(I_final)))).
%%%-------------------------------------------------------------------
- - func example_numbers = list(int).
example_numbers = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4].
main(!IO) :-
(sfc64.init(P, S)),
make_io_urandom(P, S, M, !IO),
Print_kth_greatest = (pred(K::in, di, uo) is det -->
print_kth_greatest(K, example_numbers, M)),
Print_kth_least = (pred(K::in, di, uo) is det -->
print_kth_least(K, example_numbers, M)),
print("With < as order predicate: ", !IO),
foldl(Print_kth_least, 1 `..` 10, !IO),
print_line("", !IO),
print("With > as order predicate: ", !IO),
foldl(Print_kth_greatest, 1 `..` 10, !IO),
print_line("", !IO).
- - pred print_kth_least(int::in, list(int)::in,
M::in, io::di, io::uo) is det <= urandom(M, io).
print_kth_least(K, Numbers_list, M, !IO) :-
(array.from_list(Numbers_list, Arr0)),
quickselect(<, K - 1, Arr0, _, Elem, M, !IO),
print(" ", !IO),
print(Elem, !IO).
- - pred print_kth_greatest(int::in, list(int)::in,
M::in, io::di, io::uo) is det <= urandom(M, io).
print_kth_greatest(K, Numbers_list, M, !IO) :-
(array.from_list(Numbers_list, Arr0)),
%% Notice that the "Less_than" predicate is actually "greater %% than". :) One can think of this as meaning that a greater number %% has an *ordinal* that is "less than"; that is, it "comes before" %% in the order. quickselect(>, K - 1, Arr0, _, Elem, M, !IO),
print(" ", !IO),
print(Elem, !IO).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</lang>
- Output:
$ mmc quickselect_task.m && ./quickselect_task With < as order predicate: 0 1 2 3 4 5 6 7 8 9 With > as order predicate: 9 8 7 6 5 4 3 2 1 0
NetRexx
<lang 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 </lang>
- 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
Nim
<lang nim>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)</lang>
Output:
0: 0 1: 1 2: 2 3: 3 4: 4 5: 5 6: 6 7: 7 8: 8 9: 9
OCaml
<lang 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</lang>
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|]
PARI/GP
<lang parigp>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) )
};</lang>
Perl
<lang 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 }
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
Phix
sequence s = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4} function quick_select(integer k) integer left = 1, right = length(s) while left<right do object pivotv = s[k]; {s[k], s[right]} = {s[right], s[k]} integer pos = left for i=left to right do if s[i]<pivotv then {s[i], s[pos]} = {s[pos], s[i]} pos += 1 end if end for {s[right], s[pos]} = {s[pos], s[right]} if pos==k then exit end if if pos<k then left = pos + 1 else right = pos - 1 end if end while return s[k] end function for i=1 to 10 do integer r = quick_select(i) printf(1," %d",r) end for {} = wait_key()
- Output:
0 1 2 3 4 5 6 7 8 9
PicoLisp
<lang PicoLisp>(seed (in "/dev/urandom" (rd 8))) (de swapL (Lst X Y)
(let L (nth Lst Y)
(swap
L
(swap (nth Lst X) (car L)) ) ) )
(de partition (Lst L R P)
(let V (get Lst P)
(swapL Lst R P)
(for I (range L R)
(and
(> V (get Lst I))
(swapL Lst L I)
(inc 'L) ) )
(swapL Lst L R)
L ) )
(de quick (Lst N L R)
(default L (inc N) R (length Lst))
(if (= L R)
(get Lst L)
(let P (partition Lst L R (rand L R))
(cond
((= N P) (get Lst N))
((> P N) (quick Lst N L P))
(T (quick Lst N P R)) ) ) ) )
(let Lst (9 8 7 6 5 0 1 2 3 4)
(println
(mapcar
'((N) (quick Lst N))
(range 0 9) ) ) )</lang>
- Output:
(0 1 2 3 4 5 6 7 8 9)
PL/I
<lang 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;</lang> 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
PowerShell
<lang PowerShell>
function partition($list, $left, $right, $pivotIndex) {
$pivotValue = $list[$pivotIndex]
$list[$pivotIndex], $list[$right] = $list[$right], $list[$pivotIndex]
$storeIndex = $left
foreach ($i in $left..($right-1)) {
if ($list[$i] -lt $pivotValue) {
$list[$storeIndex],$list[$i] = $list[$i], $list[$storeIndex]
$storeIndex += 1
}
}
$list[$right],$list[$storeIndex] = $list[$storeIndex], $list[$right]
$storeIndex
}
function rank($list, $left, $right, $n) {
if ($left -eq $right) {$list[$left]}
else {
$pivotIndex = Get-Random -Minimum $left -Maximum $right
$pivotIndex = partition $list $left $right $pivotIndex
if ($n -eq $pivotIndex) {$list[$n]}
elseif ($n -lt $pivotIndex) {(rank $list $left ($pivotIndex - 1) $n)}
else {(rank $list ($pivotIndex+1) $right $n)}
}
}
function quickselect($list) {
$right = $list.count-1
foreach($left in 0..$right) {rank $list $left $right $left}
} $arr = @(9, 8, 7, 6, 5, 0, 1, 2, 3, 4) "$(quickselect $arr)" </lang> Output:
0 1 2 3 4 5 6 7 8 9
PureBasic
A direct implementation of the Wikipedia pseudo-code. <lang PureBasic> Procedure QuickPartition (Array L(1), left, right, pivotIndex)
pivotValue = L(pivotIndex)
Swap L(pivotIndex) , L(right); Move pivot To End
storeIndex = left
For i=left To right-1
If L(i) < pivotValue
Swap L(storeIndex),L(i)
storeIndex+1
EndIf
Next i
Swap L(right), L(storeIndex) ; Move pivot To its final place
ProcedureReturn storeIndex
EndProcedure
Procedure QuickSelect(Array L(1), left, right, k)
Repeat
If left = right:ProcedureReturn L(left):EndIf
pivotIndex.i= left; Select pivotIndex between left And right
pivotIndex= QuickPartition(L(), left, right, pivotIndex)
If k = pivotIndex
ProcedureReturn L(k)
ElseIf k < pivotIndex
right= pivotIndex - 1
Else
left= pivotIndex + 1
EndIf
ForEver
EndProcedure Dim L.i(9) For i=0 To 9
Read L(i)
Next i DataSection
Data.i 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
EndDataSection For i=0 To 9
Debug QuickSelect(L(),0,9,i)
Next i</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
Python
Procedural
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. <lang python>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)])</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Composition of pure functions
<lang python>Quick select
from functools import reduce
- quickselect :: Ord a => Int -> [a] -> a
def quickSelect(k):
The kth smallest element
in the unordered list xs.
def go(k, xs):
x = xs[0]
def ltx(y):
return y < x
ys, zs = partition(ltx)(xs[1:])
n = len(ys)
return go(k, ys) if k < n else (
go(k - n - 1, zs) if k > n else x
)
return lambda xs: go(k, xs) if xs else None
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Test
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print(list(map(
flip(quickSelect)(v),
range(0, len(v))
)))
- GENERIC -------------------------------------------------
- flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
The (curried) function f with its
arguments reversed.
return lambda a: lambda b: f(b)(a)
- partition :: (a -> Bool) -> [a] -> ([a], [a])
def partition(p):
The pair of lists of those elements in xs
which respectively do, and don't
satisfy the predicate p.
def go(a, x):
ts, fs = a
return (ts + [x], fs) if p(x) else (ts, fs + [x])
return lambda xs: reduce(go, xs, ([], []))
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Racket
<lang 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)))) ", ")) </lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Raku
(formerly Perl 6)
<lang perl6>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 More {
$right = $pivot-new-index - 1;
}
when Less {
$k -= $pivot-dist;
$left = $pivot-new-index + 1;
}
}
}
}</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
REXX
uses in-line swap
<lang rexx>/*REXX program sorts a list (which may be numbers) by using the quick select algorithm.*/ parse arg list; if list= then list= 9 8 7 6 5 0 1 2 3 4 /*Not given? Use default.*/ say right('list: ', 22) list
- = words(list)
do i=1 for #; @.i= word(list, i) /*assign all the items ──► @. (array). */
end /*i*/ /* [↑] #: number of items in the list.*/
say
do j=1 for # /*show 1 ──► # items place and value.*/
say right('item', 20) right(j, length(#))", value: " qSel(1, #, j)
end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ qPart: procedure expose @.; parse arg L 1 ?,R,X; xVal= @.X
parse value @.X @.R with @.R @.X /*swap the two names items (X and R). */
do k=L to R-1 /*process the left side of the list. */
if @.k>xVal then iterate /*when an item > item #X, then skip it.*/
parse value @.? @.k with @.k @.? /*swap the two named items (? and K). */
?= ? + 1 /*bump the item number (point to next).*/
end /*k*/
parse value @.R @.? with @.? @.R /*swap the two named items (R and ?). */
return ? /*return the item number to invoker. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ qSel: procedure expose @.; parse arg L,R,z; if L==R then return @.L /*only one item?*/
do forever /*keep searching until we're all done. */
new= qPart(L, R, (L+R) % 2) /*partition the list into roughly ½. */
$= new - L + 1 /*calculate pivot distance less L+1. */
if $==z then return @.new /*we're all done with this pivot part. */
else if z<$ then R= new-1 /*decrease the right half of the array.*/
else do; z= z-$ /*decrease the distance. */
L= new+1 /*increase the left half *f the array.*/
end
end /*forever*/</lang>
- output when using the default input:
list: 9 8 7 6 5 0 1 2 3 4
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
uses swap subroutine
<lang rexx>/*REXX program sorts a list (which may be numbers) by using the quick select algorithm. */ parse arg list; if list= then list= 9 8 7 6 5 0 1 2 3 4 /*Not given? Use default.*/ say right('list: ', 22) list
- = words(list)
do i=1 for #; @.i= word(list, i) /*assign all the items ──► @. (array). */
end /*i*/ /* [↑] #: number of items in the list.*/
say
do j=1 for # /*show 1 ──► # items place and value.*/
say right('item', 20) right(j, length(#))", value: " qSel(1, #, j)
end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ qPart: procedure expose @.; parse arg L 1 ?,R,X; xVal= @.X
call swap X,R /*swap the two named items (X and R). */
do k=L to R-1 /*process the left side of the list. */
if @.k>xVal then iterate /*when an item > item #X, then skip it.*/
call swap ?,k /*swap the two named items (? and K). */
?= ? + 1 /*bump the item number (point to next).*/
end /*k*/
call swap R,? /*swap the two named items (R and ?). */
return ? /*return the item number to invoker. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ qSel: procedure expose @.; parse arg L,R,z; if L==R then return @.L /*only one item?*/
do forever /*keep searching until we're all done. */
new= qPart(L, R, (L+R) % 2) /*partition the list into roughly ½. */
$= new - L + 1 /*calculate the pivot distance less L+1*/
if $==z then return @.new /*we're all done with this pivot part. */
else if z<$ then R= new-1 /*decrease the right half of the array.*/
else do; z= z-$ /*decrease the distance. */
L= new+1 /*increase the left half of the array.*/
end
end /*forever*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ swap: parse arg _1,_2; parse value @._1 @._2 with @._2 @._1; return /*swap 2 items.*/</lang>
- output is the identical to the 1st REXX version.
Ring
<lang ring> aList = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] see partition(aList, 9, 4, 2) + nl
func partition list, left, right, pivotIndex
pivotValue = list[pivotIndex]
temp = list[pivotIndex]
list[pivotIndex] = list[right]
list[right] = temp
storeIndex = left
for i = left to right-1
if list[i] < pivotValue
temp = list[storeIndex]
list[storeIndex] = list[i]
list[i] = temp
storeIndex++ ok
temp = list[right]
list[right] = list[storeIndex]
list[storeIndex] = temp
next
return storeIndex
</lang>
Ruby
<lang 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) }</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Rust
<lang rust>// See https://en.wikipedia.org/wiki/Quickselect
fn partition<T: PartialOrd>(a: &mut [T], left: usize, right: usize, pivot: usize) -> usize {
a.swap(pivot, right);
let mut store_index = left;
for i in left..right {
if a[i] < a[right] {
a.swap(store_index, i);
store_index += 1;
}
}
a.swap(right, store_index);
store_index
}
fn pivot_index(left: usize, right: usize) -> usize {
return left + (right - left) / 2;
}
fn select<T: PartialOrd>(a: &mut [T], mut left: usize, mut right: usize, n: usize) {
loop {
if left == right {
break;
}
let mut pivot = pivot_index(left, right);
pivot = partition(a, left, right, pivot);
if n == pivot {
break;
} else if n < pivot {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
}
// Rearranges the elements of 'a' such that the element at index 'n' is // the same as it would be if the array were sorted, smaller elements are // to the left of it and larger elements are to its right. fn nth_element<T: PartialOrd>(a: &mut [T], n: usize) {
select(a, 0, a.len() - 1, n);
}
fn main() {
let a = vec![9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
for n in 0..a.len() {
let mut b = a.clone();
nth_element(&mut b, n);
println!("n = {}, nth element = {}", n + 1, b[n]);
}
}</lang>
- Output:
n = 1, nth element = 0 n = 2, nth element = 1 n = 3, nth element = 2 n = 4, nth element = 3 n = 5, nth element = 4 n = 6, nth element = 5 n = 7, nth element = 6 n = 8, nth element = 7 n = 9, nth element = 8 n = 10, nth element = 9
Scala
<lang 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(", "))
}
}</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Scheme
The program is written in R7RS-small Scheme. It will run on CHICKEN 5 Scheme if you have the necessary eggs installed and use the "-R r7rs" option.
<lang scheme>;;
- Quickselect with random pivot.
- Such a pivot provides O(n) worst-case *expected* time.
- One can get true O(n) time by using "median of medians" to choose
- the pivot, but quickselect with a median of medians pivot is a
- complicated algorithm. See
- https://en.wikipedia.org/w/index.php?title=Median_of_medians&oldid=1082505985
- Random pivot has the further advantage that it does not require any
- comparisons of array elements.
- By the way, SRFI-132 specifies that vector-select! have O(n)
- running time, and yet the reference implementation (as of 21 May
- 2022) uses random pivot. I am pretty sure you cannot count on an
- implementation having "true" O(n) behavior.
(import (scheme base)) (import (scheme case-lambda)) (import (scheme write)) (import (only (scheme process-context) exit)) (import (only (srfi 27) random-integer))
(define (vector-swap! vec i j)
(let ((xi (vector-ref vec i))
(xj (vector-ref vec j)))
(vector-set! vec i xj)
(vector-set! vec j xi)))
(define (search-right <? pivot i j vec)
(let loop ((i i))
(cond ((= i j) i)
((<? pivot (vector-ref vec i)) i)
(else (loop (+ i 1))))))
(define (search-left <? pivot i j vec)
(let loop ((j j))
(cond ((= i j) j)
((<? (vector-ref vec j) pivot) j)
(else (loop (- j 1))))))
(define (partition <? pivot i-first i-last vec)
;; Partition a subvector into two halves: one with elements less
;; than or equal to a pivot, the other with elements greater than or
;; equal to a pivot. Returns an index where anything less than the
;; pivot is to the left of the index, and anything greater than the
;; pivot is either at the index or to its right. The implementation
;; is tail-recursive.
(let loop ((i (- i-first 1))
(j (+ i-last 1)))
(if (= i j)
i
(let ((i (search-right <? pivot (+ i 1) j vec)))
(if (= i j)
i
(let ((j (search-left <? pivot i (- j 1) vec)))
(vector-swap! vec i j)
(loop i j)))))))
(define (partition-around-random-pivot <? i-first i-last vec)
(let* ((i-pivot (+ i-first (random-integer (- i-last i-first -1))))
(pivot (vector-ref vec i-pivot)))
;; Move the last element to where the pivot had been. Perhaps the ;; pivot was already the last element, of course. In any case, we ;; shall partition only from I_first to I_last - 1. (vector-set! vec i-pivot (vector-ref vec i-last))
;; Partition the array in the range I_first..I_last - 1, leaving ;; out the last element (which now can be considered garbage). (let ((i-final (partition <? pivot i-first (- i-last 1) vec)))
;; Now everything that is less than the pivot is to the left of
;; I_final.
;; Put the pivot at I_final, moving the element that had been
;; there to the end. If I_final = I_last, then this element is
;; actually garbage and will be overwritten with the pivot,
;; which turns out to be the greatest element. Otherwise, the
;; moved element is not less than the pivot and so the
;; partitioning is preserved.
(vector-set! vec i-last (vector-ref vec i-final))
(vector-set! vec i-final pivot)
;; Return i-final, the final position of the pivot element.
i-final)))
(define quickselect!
(case-lambda
((<? vec k)
;; Select the (k+1)st least element of vec.
(quickselect! <? 0 (- (vector-length vec) 1) vec k))
((<? i-first i-last vec k)
;; Select the (k+1)st least element of vec[i-first..i-last].
(unless (and (<= 0 k) (<= k (- i-last i-first)))
;; Here you more likely want to raise an exception, but how to
;; do so is not specified in R7RS small. (It *is* specified in
;; R6RS, but R6RS features are widely unsupported by Schemes.)
(display "out of range" (current-error-port))
(exit 1))
(let ((k (+ k i-first))) ; Adjust k for index range.
(let loop ((i-first i-first)
(i-last i-last))
(if (= i-first i-last)
(vector-ref vec i-first)
(let ((i-final (partition-around-random-pivot
<? i-first i-last vec)))
;; Compare i-final and k, to see what to do next.
(cond ((< i-final k) (loop (+ i-final 1) i-last))
((< k i-final) (loop i-first (- i-final 1)))
(else (vector-ref vec i-final))))))))))
(define (print-kth <? k numbers-vector)
(let* ((vec (vector-copy numbers-vector))
(elem (quickselect! <? vec (- k 1))))
(display " ")
(display elem)))
(define example-numbers #(9 8 7 6 5 0 1 2 3 4))
(display "With < as ordering predicate: ") (do ((k 1 (+ k 1)))
((= k 11)) (print-kth < k example-numbers))
(newline) (display "With > as ordering predicate: ") (do ((k 1 (+ k 1)))
((= k 11)) (print-kth > k example-numbers))
(newline)</lang>
- Output:
$ gosh quickselect_task.scm With < as ordering predicate: 0 1 2 3 4 5 6 7 8 9 With > as ordering predicate: 9 8 7 6 5 4 3 2 1 0
Sidef
<lang ruby>func quickselect(a, k) {
var pivot = a.pick;
var left = a.grep{|i| i < pivot};
var right = a.grep{|i| i > pivot};
given(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)};</lang>
- Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Standard ML
<lang sml>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</lang>
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
Swift
<lang 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()</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Tcl
<lang tcl># 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}] }
}
}</lang> Demonstrating: <lang tcl>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]"
}</lang>
- Output:
1 => 0 2 => 1 3 => 2 4 => 3 5 => 4 6 => 5 7 => 6 8 => 7 9 => 8 10 => 9
VBA
<lang vb>Dim s As Variant
Private Function quick_select(ByRef s As Variant, k As Integer) As Integer
Dim left As Integer, right As Integer, pos As Integer
Dim pivotValue As Integer, tmp As Integer
left = 1: right = UBound(s)
Do While left < right
pivotValue = s(k)
tmp = s(k)
s(k) = s(right)
s(right) = tmp
pos = left
For i = left To right
If s(i) < pivotValue Then
tmp = s(i)
s(i) = s(pos)
s(pos) = tmp
pos = pos + 1
End If
Next i
tmp = s(right)
s(right) = s(pos)
s(pos) = tmp
If pos = k Then
Exit Do
End If
If pos < k Then
left = pos + 1
Else
right = pos - 1
End If
Loop
quick_select = s(k)
End Function Public Sub main()
Dim r As Integer, i As Integer
s = [{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}]
For i = 1 To 10
r = quick_select(s, i) 's is ByRef parameter
Debug.Print IIf(i < 10, r & ", ", "" & r);
Next i
End Sub
</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Wren
The Find.quick method in the above module implements the quickselect algorithm. <lang ecmascript>import "/sort" for Find
var a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] for (k in 0..9) {
System.write(Find.quick(a, k))
if (k < 9) System.write(", ")
} System.print()</lang>
- Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
zkl
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) <lang zkl>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);
}</lang> <lang zkl>list:=T(10, 9, 8, 7, 6, 1, 2, 3, 4, 5); foreach nth in (list.len()){ println(nth,": ",qselect(list,nth)) }</lang>
- Output:
0: 1 1: 2 2: 3 3: 4 4: 5 5: 6 6: 7 7: 8 8: 9 9: 10
- Programming Tasks
- Sorting Algorithms
- Sorting
- 11l
- Action!
- ALGOL 68
- AppleScript
- Arturo
- AutoHotkey
- C
- C sharp
- C++
- CLU
- COBOL
- Common Lisp
- Crystal
- D
- Delphi
- System.SysUtils
- EasyLang
- Elixir
- Erlang
- F Sharp
- Factor
- Fortran
- FreeBASIC
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- Maple
- Mathematica
- Wolfram Language
- Mercury
- NetRexx
- Nim
- OCaml
- PARI/GP
- Perl
- Phix
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- Racket
- Raku
- REXX
- Ring
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Standard ML
- Swift
- Tcl
- VBA
- Wren
- Wren-sort
- Zkl