Quickselect algorithm

From Rosetta Code
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.

11l

Translation of: Python
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)))
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
or android 64 bits with application Termux
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program quickSelection64.s   */
/* look pseudo code in wikipedia  quickselect */

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResultIndex:        .asciz "index  : "
szMessResultValue:        .asciz " value  : "
szCarriageReturn:         .asciz "\n"
szMessStart:          .asciz "Program 64 bits start.\n"
.align 4
TableNumber:	          .quad   9, 8, 7, 6, 5, 0, 1, 2, 3, 4
.equ NBELEMENTS,      (. - TableNumber) / 8
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:             .skip 24
sZoneConv1:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                    // entry of program 
    ldr x0,qAdrszMessStart
    bl affichageMess
    mov x6,#0
1:
    ldr x0,qAdrTableNumber               // address number table
    mov x1,#0                            // index first item
    mov x2,#NBELEMENTS -1                // index last item 
    mov x3,x6                            // search index
    bl select                            // call selection
    ldr x1,qAdrsZoneConv
    bl conversion10                      // convert result to decimal
    mov x0,x6
    ldr x1,qAdrsZoneConv1
    bl conversion10                      // convert index to decimal
    mov x0,#5                            // and display result
    ldr x1,qAdrszMessResultIndex
    ldr x2,qAdrsZoneConv1
    ldr x3,qAdrszMessResultValue
    ldr x4,qAdrsZoneConv
    ldr x5,qAdrszCarriageReturn
    bl displayStrings
    add x6,x6,#1
    cmp x6,#NBELEMENTS
    blt 1b

100:                                     // standard end of the program 
    mov x0, #0                           // return code
    mov x8, #EXIT                        // request to exit program
    svc #0                               // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrTableNumber:          .quad TableNumber
qAdrsZoneConv:            .quad sZoneConv
qAdrsZoneConv1:           .quad sZoneConv1
qAdrszMessResultIndex:    .quad szMessResultIndex
qAdrszMessResultValue:    .quad szMessResultValue
qAdrszMessStart:          .quad szMessStart
/***************************************************/
/*   Appel récursif selection                      */
/***************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item  */
/* x2 contains index of last item   */
/* x3 contains search index */
select:
    stp x1,lr,[sp,-16]!            // save  registers
    stp x2,x3,[sp,-16]!            // save  registers
    stp x4,x5,[sp,-16]!            // save  registers
    stp x6,x7,[sp,-16]!            // save  registers
    mov x6,x3                      // save search index
    cmp x1,x2                      // first = last ? 
    bne 1f
    ldr x0,[x0,x1,lsl #3]          // return value of first index
    b 100f                         // yes -> end
1:
    add x3,x1,x2
    lsr x3,x3,#1                   // compute median pivot 
    mov x4,x0                      // save x0
    mov x5,x2                      // save x2
    bl partition                   // cutting.quado 2 parts
    cmp x6,x0                      // pivot is ok ?
    bne 2f
    ldr x0,[x4,x0,lsl #3]          // yes -> return value
    b 100f
 2:
    bgt 3f
    sub x2,x0,#1                   // index partition  - 1 
    mov x0,x4                      // array address
    mov x3,x6                      // search index
    bl select                      // select lower part
    b 100f
3:
    add x1,x0,#1                   // index begin = index partition + 1
    mov x0,x4                      // array address
    mov x2,x5                      // last item
    mov x3,x6                      // search index
    bl select                      // select higter part
 
 100:                              // end function
    ldp x6,x7,[sp],16              // restaur  2 registers
    ldp x4,x5,[sp],16              // restaur  2 registers
    ldp x2,x3,[sp],16              // restaur  2 registers
    ldp x1,lr,[sp],16              // restaur  2 registers
    ret                            // return to address lr x30
/******************************************************************/
/*      Partition table elements                                */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item  */
/* x2 contains index of last item   */
/* x3 contains index of pivot */
partition:
    stp x1,lr,[sp,-16]!            // save  registers
    stp x2,x3,[sp,-16]!            // save  registers
    stp x4,x5,[sp,-16]!            // save  registers
    stp x6,x7,[sp,-16]!            // save  registers
    ldr x4,[x0,x3,lsl #3]          // load value of pivot
    ldr x5,[x0,x2,lsl #3]          // load value last index
    str x5,[x0,x3,lsl #3]          // swap value of pivot
    str x4,[x0,x2,lsl #3]          // and value last index
    mov x3,x1                      // init with first index
1:                                 // begin loop
    ldr x6,[x0,x3,lsl #3]          // load value
    cmp x6,x4                      // compare loop value and pivot value
    bge 2f
    ldr x5,[x0,x1,lsl #3]          // if < swap value table
    str x6,[x0,x1,lsl #3]
    str x5,[x0,x3,lsl #3]
    add x1,x1,#1                   // and increment index 1
2:
    add x3,x3,#1                   // increment index 2
    cmp x3,x2                      // end ?
    blt 1b                         // no loop
    ldr x5,[x0,x1,lsl #3]          // swap value
    str x4,[x0,x1,lsl #3]
    str x5,[x0,x2,lsl #3]
    mov x0,x1                      // return index partition
100:
    ldp x6,x7,[sp],16              // restaur  2 registers
    ldp x4,x5,[sp],16              // restaur  2 registers
    ldp x2,x3,[sp],16              // restaur  2 registers
    ldp x1,lr,[sp],16              // restaur  2 registers
    ret                            // return to address lr x30
    
 /***************************************************/
/*   display multi strings                         */
/*   new version 24/05/2023                        */
/***************************************************/
/* x0  contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* x4 address string4 */
/* x5 address string5 */
/* x6 address string5 */
/* x7 address string6 */
displayStrings:            // INFO:  displayStrings
    stp x8,lr,[sp,-16]!    // save  registers 
    stp x2,fp,[sp,-16]!    // save  registers 
    add fp,sp,#32          // save paraméters address (4 registers saved * 8 bytes)
    mov x8,x0              // save strings number
    cmp x8,#0              // 0 string -> end
    ble 100f
    mov x0,x1              // string 1
    bl affichageMess
    cmp x8,#1              // number > 1
    ble 100f
    mov x0,x2
    bl affichageMess
    cmp x8,#2
    ble 100f
    mov x0,x3
    bl affichageMess
    cmp x8,#3
    ble 100f
    mov x0,x4
    bl affichageMess
    cmp x8,#4
    ble 100f
    mov x0,x5
    bl affichageMess
    cmp x8,#5
    ble 100f
    mov x0,x6
    bl affichageMess
    cmp x8,#6
    ble 100f
    mov x0,x7
    bl affichageMess
    
100:
    ldp x2,fp,[sp],16        // restaur  registers 
    ldp x8,lr,[sp],16        // restaur  registers
    ret
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
Output:
Program 64 bits start.
index  : 0 value  : 0
index  : 1 value  : 1
index  : 2 value  : 2
index  : 3 value  : 3
index  : 4 value  : 4
index  : 5 value  : 5
index  : 6 value  : 6
index  : 7 value  : 7
index  : 8 value  : 8
index  : 9 value  : 9

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
Output:

Screenshot from Atari 8-bit computer

0 1 2 3 4 5 6 7 8 9

Ada

Translation of: Mercury
Works with: GNAT version Community 2021


I implement a generic partition and a generic quickselect and apply them to an array of integers. The order predicate is passed as a parameter, and I demonstrate both < and > as the predicate.

----------------------------------------------------------------------

with Ada.Numerics.Float_Random;
with Ada.Text_IO;

procedure quickselect_task
is

  use Ada.Numerics.Float_Random;
  use Ada.Text_IO;

  gen : Generator;

----------------------------------------------------------------------
--
-- procedure partition
--
-- 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.
--

  generic
    type T is private;
    type T_Array is array (Natural range <>) of T;
  procedure partition
   (less_than : access function
     (x, y : T)
      return Boolean;
    pivot           : in     T;
    i_first, i_last : in     Natural;
    arr             : in out T_Array;
    i_pivot         :    out Natural);

  procedure partition
   (less_than : access function
     (x, y : T)
      return Boolean;
    pivot           : in     T;
    i_first, i_last : in     Natural;
    arr             : in out T_Array;
    i_pivot         :    out Natural)
  is
    i, j : Integer;
    temp : T;
  begin

    i := Integer (i_first) - 1;
    j := i_last + 1;

    while i /= j loop
      -- Move i so everything to the left of i is less than or equal
      -- to the pivot.
      i := i + 1;
      while i /= j and then not less_than (pivot, arr (i)) loop
        i := i + 1;
      end loop;

      -- Move j so everything to the right of j is greater than or
      -- equal to the pivot.
      if i /= j then
        j := j - 1;
        while i /= j and then not less_than (arr (j), pivot) loop
          j := j - 1;
        end loop;
      end if;

      -- Swap entries.
      temp    := arr (i);
      arr (i) := arr (j);
      arr (j) := temp;
    end loop;

    i_pivot := i;

  end partition;

----------------------------------------------------------------------
--
-- procedure quickselect
--
-- Quickselect with a random pivot. Returns the (k+1)st element of a
-- subarray, according to the given order predicate. Also rearranges
-- the subarray so that anything "less than" the (k+1)st element is to
-- the left of it, and anything "greater than" it is to its right.
--
-- 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
-- quickselect with such a pivot is a complicated algorithm requiring
-- many comparisons of array elements. A random number generator, by
-- contrast, requires no comparisons of array elements.
--

  generic
    type T is private;
    type T_Array is array (Natural range <>) of T;
  procedure quickselect
   (less_than : access function
     (x, y : T)
      return Boolean;
    i_first, i_last    : in     Natural;
    k                  : in     Natural;
    arr                : in out T_Array;
    the_element        :    out T;
    the_elements_index :    out Natural);

  procedure quickselect
   (less_than : access function
     (x, y : T)
      return Boolean;
    i_first, i_last    : in     Natural;
    k                  : in     Natural;
    arr                : in out T_Array;
    the_element        :    out T;
    the_elements_index :    out Natural)
  is
    procedure T_partition is new partition (T, T_Array);

    procedure qselect
     (less_than : access function
       (x, y : T)
        return Boolean;
      i_first, i_last    : in     Natural;
      k                  : in     Natural;
      arr                : in out T_Array;
      the_element        :    out T;
      the_elements_index :    out Natural)
    is
      i, j    : Natural;
      i_pivot : Natural;
      i_final : Natural;
      pivot   : T;
    begin

      i := i_first;
      j := i_last;

      while i /= j loop
        i_pivot :=
         i + Natural (Float'Floor (Random (gen) * Float (j - i + 1)));
        i_pivot := Natural'Min (j, i_pivot);
        pivot   := arr (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 to j - 1.
        arr (i_pivot) := arr (j);

        -- Partition the array in the range i .. j - 1, leaving out
        -- the last element (which now can be considered garbage).
        T_partition (less_than, pivot, i, j - 1, arr, 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 = j, 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.
        arr (j)       := arr (i_final);
        arr (i_final) := pivot;

        -- Compare i_final and k, to see what to do next.
        if i_final < k then
          i := i_final + 1;
        elsif k < i_final then
          j := i_final - 1;
        else
          -- Exit the loop.
          i := i_final;
          j := i_final;
        end if;
      end loop;

      the_element        := arr (i);
      the_elements_index := i;

    end qselect;
  begin
    -- Adjust k for the subarray's position.
    qselect
     (less_than, i_first, i_last, k + i_first, arr, the_element,
      the_elements_index);
  end quickselect;

----------------------------------------------------------------------

  type Integer_Array is array (Natural range <>) of Integer;

  procedure integer_quickselect is new quickselect
   (Integer, Integer_Array);

  procedure print_kth
   (less_than : access function
     (x, y : Integer)
      return Boolean;
    k               : in     Positive;
    i_first, i_last : in     Integer;
    arr             : in out Integer_Array)
  is
    copy_of_arr        : Integer_Array (0 .. i_last);
    the_element        : Integer;
    the_elements_index : Natural;
  begin
    for j in 0 .. i_last loop
      copy_of_arr (j) := arr (j);
    end loop;
    integer_quickselect
     (less_than, i_first, i_last, k - 1, copy_of_arr, the_element,
      the_elements_index);
    Put (Integer'Image (the_element));
  end print_kth;

----------------------------------------------------------------------

  example_numbers : Integer_Array := (9, 8, 7, 6, 5, 0, 1, 2, 3, 4);

  function lt
   (x, y : Integer)
    return Boolean
  is
  begin
    return (x < y);
  end lt;

  function gt
   (x, y : Integer)
    return Boolean
  is
  begin
    return (x > y);
  end gt;

begin
  Put ("With < as order predicate: ");
  for k in 1 .. 10 loop
    print_kth (lt'Access, k, 0, 9, example_numbers);
  end loop;
  Put_Line ("");
  Put ("With > as order predicate: ");
  for k in 1 .. 10 loop
    print_kth (gt'Access, k, 0, 9, example_numbers);
  end loop;
  Put_Line ("");
end quickselect_task;

----------------------------------------------------------------------
Output:
$ gnatmake -q quickselect_task.adb && ./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

ALGOL 68

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
Output:
 1:   0
 2:   1
 3:   2
 4:   3
 5:   4
 6:   5
 7:   6
 8:   7
 9:   8
10:   9

AppleScript

Procedural

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
Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Functional

----------------------- 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
Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

ARM Assembly

Works with: as version Raspberry Pi
or android 32 bits with application Termux
/* ARM assembly Raspberry PI  */
/*  program quickSelection.s   */
/* look pseudo code in wikipedia  quickselect */

/************************************/
/* Constantes                       */
/************************************/
/* for constantes see task include a file in arm assembly */
.include "../constantes.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResultIndex:        .asciz "index  : "
szMessResultValue:        .asciz " value  : "
szCarriageReturn:  .asciz "\n"
 
.align 4
TableNumber:	     .int   9, 8, 7, 6, 5, 0, 1, 2, 3, 4
.equ NBELEMENTS,      (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:             .skip 24
sZoneConv1:             .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                    @ entry of program 
    mov r5,#0
1:
    ldr r0,iAdrTableNumber               @ address number table
    mov r1,#0                            @ index first item
    mov r2,#NBELEMENTS -1                @ index last item 
    mov r3,r5                            @ search index
    bl select                            @ call selection
    ldr r1,iAdrsZoneConv
    bl conversion10                      @ convert result to decimal
    mov r0,r5
    ldr r1,iAdrsZoneConv1
    bl conversion10                      @ convert index to decimal
    mov r0,#5                            @ and display result
    ldr r1,iAdrszMessResultIndex
    ldr r2,iAdrsZoneConv1
    ldr r3,iAdrszMessResultValue
    ldr r4,iAdrsZoneConv
    push {r4}
    ldr r4,iAdrszCarriageReturn
    push {r4}
    bl displayStrings
    add sp,sp,#8                         @ stack alignement (2 push)
    add r5,r5,#1
    cmp r5,#NBELEMENTS
    blt 1b

100:                                     @ standard end of the program 
    mov r0, #0                           @ return code
    mov r7, #EXIT                        @ request to exit program
    svc #0                               @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrTableNumber:          .int TableNumber
iAdrsZoneConv:            .int sZoneConv
iAdrsZoneConv1:           .int sZoneConv1
iAdrszMessResultIndex:    .int szMessResultIndex
iAdrszMessResultValue:    .int szMessResultValue

/***************************************************/
/*   Appel récursif selection           */
/***************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item  */
/* r2 contains index of last item   */
/* r3 contains search index */
select:
    push {r1-r6,lr}                @ save registers
    mov r6,r3                      @ save search index
    cmp r1,r2                      @ first = last ? 
    ldreq r0,[r0,r1,lsl #2]        @ return value of first index
    beq 100f                       @ yes -> end
    add r3,r1,r2
    lsr r3,r3,#1                   @ compute median pivot 
    mov r4,r0                      @ save r0
    mov r5,r2                      @ save r2
    bl partition                   @ cutting into 2 parts
    cmp r6,r0                      @ pivot is ok ?
    ldreq r0,[r4,r0,lsl #2]        @ return value
    beq 100f
    bgt 1f
    sub r2,r0,#1                   @ index partition  - 1 
    mov r0,r4                      @ array address
    mov r3,r6                      @ search index
    bl select                      @ select lower part
    b 100f
1:
    add r1,r0,#1                   @ index begin = index partition + 1
    mov r0,r4                      @ array address
    mov r2,r5                      @ last item
    mov r3,r6                      @ search index
    bl select                      @ select higter part
 100:                              @ end function
    pop {r1-r6,pc}                 @ restaur  register
/******************************************************************/
/*      Partition table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item  */
/* r2 contains index of last item   */
/* r3 contains index of pivot */
partition:
    push {r1-r6,lr}                                    @ save registers
    ldr r4,[r0,r3,lsl #2]                              @ load value of pivot
    ldr r5,[r0,r2,lsl #2]                              @ load value last index
    str r5,[r0,r3,lsl #2]                              @ swap value of pivot
    str r4,[r0,r2,lsl #2]                              @ and value last index
    mov r3,r1                                          @ init with first index
1:                                                     @ begin loop
    ldr r6,[r0,r3,lsl #2]                              @ load value
    cmp r6,r4                                          @ compare loop value and pivot value
    ldrlt r5,[r0,r1,lsl #2]                            @ if < swap value table
    strlt r6,[r0,r1,lsl #2]
    strlt r5,[r0,r3,lsl #2]
    addlt r1,#1                                        @ and increment index 1
    add r3,#1                                          @ increment index 2
    cmp r3,r2                                          @ end ?
    blt 1b                                             @ no loop
    ldr r5,[r0,r1,lsl #2]                              @ swap value
    str r4,[r0,r1,lsl #2]
    str r5,[r0,r2,lsl #2]
    mov r0,r1                                          @ return index partition
100:
    pop {r1-r6,pc}
    
/***************************************************/
/*   display multi strings                    */
/***************************************************/
/* r0  contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add  number other address * 4 to add to the stack */
displayStrings:            @ INFO:  displayStrings
    push {r1-r4,fp,lr}     @ save des registres
    add fp,sp,#24          @ save paraméters address (6 registers saved * 4 bytes)
    mov r4,r0              @ save strings number
    cmp r4,#0              @ 0 string -> end
    ble 100f
    mov r0,r1              @ string 1
    bl affichageMess
    cmp r4,#1              @ number > 1
    ble 100f
    mov r0,r2
    bl affichageMess
    cmp r4,#2
    ble 100f
    mov r0,r3
    bl affichageMess
    cmp r4,#3
    ble 100f
    mov r3,#3
    sub r2,r4,#4
1:                         @ loop extract address string on stack
    ldr r0,[fp,r2,lsl #2]
    bl affichageMess
    subs r2,#1
    bge 1b
100:
    pop {r1-r4,fp,pc}    
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"
Output:
index  : 0           value  : 0
index  : 1           value  : 1
index  : 2           value  : 2
index  : 3           value  : 3
index  : 4           value  : 4
index  : 5           value  : 5
index  : 6           value  : 6
index  : 7           value  : 7
index  : 8           value  : 8
index  : 9           value  : 9

Arturo

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
Output:
0 1 2 3 4 5 6 7 8 9

ATS

Quickselect working on linear lists

There is also a stable quicksort here. See it demonstrated at the quicksort task.

(*------------------------------------------------------------------*)
(*

  For linear linked lists, using a random pivot:

    * stable three-way "separation" (a variant of quickselect)
    * quickselect
    * stable quicksort

  Also a couple of routines for splitting lists according to a
  predicate.

  Linear list operations are destructive but may avoid doing many
  unnecessary allocations. Also they do not require a garbage
  collector.

*)

#include "share/atspre_staload.hats"

staload UN = "prelude/SATS/unsafe.sats"

#define NIL list_vt_nil ()
#define ::  list_vt_cons

(*------------------------------------------------------------------*)
(* A simple linear congruential generator for pivot selection.      *)

(* The multiplier lcg_a comes from Steele, Guy; Vigna, Sebastiano (28
   September 2021). "Computationally easy, spectrally good multipliers
   for congruential pseudorandom number generators".
   arXiv:2001.05304v3 [cs.DS] *)
macdef lcg_a = $UN.cast{uint64} 0xf1357aea2e62a9c5LLU

(* lcg_c must be odd. *)
macdef lcg_c = $UN.cast{uint64} 0xbaceba11beefbeadLLU

var seed : uint64 = $UN.cast 0
val p_seed = addr@ seed

fn
random_double () :<!wrt> double =
  let
    val (pf, fpf | p_seed) = $UN.ptr0_vtake{uint64} p_seed
    val old_seed = ptr_get<uint64> (pf | p_seed)

    (* IEEE "binary64" or "double" has 52 bits of precision. We will
       take the high 48 bits of the seed and divide it by 2**48, to
       get a number 0.0 <= randnum < 1.0 *)
    val high_48_bits = $UN.cast{double} (old_seed >> 16)
    val divisor = $UN.cast{double} (1LLU << 48)
    val randnum = high_48_bits / divisor

    (* The following operation is modulo 2**64, by virtue of standard
       C behavior for uint64_t. *)
    val new_seed = (lcg_a * old_seed) + lcg_c

    val () = ptr_set<uint64> (pf | p_seed, new_seed)
    prval () = fpf pf
  in
    randnum
  end

(*------------------------------------------------------------------*)

(* Destructive split into two lists: a list of leading elements that
   satisfy a predicate, and the tail of that split. (This is similar
   to "span!" in SRFI-1.) *)
extern fun {a : vt@ype}
list_vt_span {n    : int}
             (pred : &((&a) -<cloptr1> bool),
              lst  : list_vt (a, n))
    : [n1, n2 : nat | n1 + n2 == n]
      @(list_vt (a, n1),
        list_vt (a, n2))

(* Destructive, stable partition into elements less than the pivot,
   elements equal to the pivot, and elements greater than the
   pivot. *)
extern fun {a : vt@ype}
list_vt_three_way_partition
          {n       : int}
          (compare : &((&a, &a) -<cloptr1> int),
           pivot   : &a,
           lst     : list_vt (a, n))
    : [n1, n2, n3 : nat | n1 + n2 + n3 == n]
      @(list_vt (a, n1),
        list_vt (a, n2),
        list_vt (a, n3))

(* Destructive, stable partition into elements less than the kth least
   element, elements equal to it, and elements greater than it. *)
extern fun {a : vt@ype}
list_vt_three_way_separation
          {n, k    : int | 0 <= k; k < n}
          (compare : &((&a, &a) -<cloptr1> int),
           k       : int k,
           lst     : list_vt (a, n))
    : [n1, n2, n3 : nat | n1 + n2 + n3 == n;
                          n1 <= k; k < n1 + n2]
      @(int n1, list_vt (a, n1),
        int n2, list_vt (a, n2),
        int n3, list_vt (a, n3))

(* Destructive quickselect for linear elements. *)
extern fun {a : vt@ype}
list_vt_select_linear
          {n, k    : int | 0 <= k; k < n}
          (compare : &((&a, &a) -<cloptr1> int),
           k       : int k,
           lst     : list_vt (a, n)) : a
extern fun {a : vt@ype}
list_vt_select_linear$clear (x : &a >> a?) : void

(* Destructive quickselect for non-linear elements. *)
extern fun {a : t@ype}
list_vt_select
          {n, k    : int | 0 <= k; k < n}
          (compare : &((&a, &a) -<cloptr1> int),
           k       : int k,
           lst     : list_vt (a, n)) : a

(* Stable quicksort. Also returns the length. *)
extern fun {a : vt@ype}
list_vt_stable_sort
          {n       : int}
          (compare : &((&a, &a) -<cloptr1> int),
           lst     : list_vt (a, n))
    : @(int n, list_vt (a, n))

(*------------------------------------------------------------------*)

implement {a}
list_vt_span {n} (pred, lst) =
  let
    fun
    loop {n      : nat} .<n>.
         (pred   : &((&a) -<cloptr1> bool),
          cursor : &list_vt (a, n) >> list_vt (a, m),
          tail   : &List_vt a? >> list_vt (a, n - m))
        : #[m : nat | m <= n] void =
      case+ cursor of
      | NIL => tail := NIL
      | @ elem :: rest =>
        if pred (elem) then
          (* elem satisfies the predicate. Move the cursor to the next
             cons-pair in the list. *)
          let
            val () = loop {n - 1} (pred, rest, tail)
            prval () = fold@ cursor
          in
          end
        else
          (* elem does not satisfy the predicate. Split the list at
             the cursor. *)
          let
            prval () = fold@ cursor
            val () = tail := cursor
            val () = cursor := NIL
          in
          end

    prval () = lemma_list_vt_param lst

    var cursor = lst
    var tail : List_vt a?
    val () = loop {n} (pred, cursor, tail)
  in
    @(cursor, tail)
  end

(*------------------------------------------------------------------*)

implement {a}
list_vt_three_way_partition {n} (compare, pivot, lst) =
  //
  // WARNING: This implementation is NOT tail-recursive.
  //
  let
    var current_sign : int = 0

    val p_compare = addr@ compare
    val p_pivot = addr@ pivot
    val p_current_sign = addr@ current_sign

    var pred =                  (* A linear closure. *)
      lam (elem : &a) : bool =<cloptr1>
        (* Return true iff the sign of the comparison of elem with the
           pivot matches the current_sign. *)
        let
          val @(pf_compare, fpf_compare | p_compare) =
            $UN.ptr0_vtake{(&a, &a) -<cloptr1> int} p_compare
          val @(pf_pivot, fpf_pivot | p_pivot) =
            $UN.ptr0_vtake{a} p_pivot
          val @(pf_current_sign, fpf_current_sign | p_current_sign) =
            $UN.ptr0_vtake{int} p_current_sign

          macdef compare = !p_compare
          macdef pivot = !p_pivot
          macdef current_sign = !p_current_sign

          val sign = compare (elem, pivot)
          val truth =
            (sign < 0 && current_sign < 0) ||
            (sign = 0 && current_sign = 0) ||
            (sign > 0 && current_sign > 0)

          prval () = fpf_compare pf_compare
          prval () = fpf_pivot pf_pivot
          prval () = fpf_current_sign pf_current_sign
        in
          truth
        end

    fun
    recurs {n            : nat}
           (compare      : &((&a, &a) -<cloptr1> int),
            pred         : &((&a) -<cloptr1> bool),
            pivot        : &a,
            current_sign : &int,
            lst          : list_vt (a, n))
          : [n1, n2, n3 : nat | n1 + n2 + n3 == n]
            @(list_vt (a, n1),
              list_vt (a, n2),
              list_vt (a, n3)) =
      case+ lst of
      | ~ NIL => @(NIL, NIL, NIL)
      | @ elem :: tail =>
        let
          macdef append = list_vt_append<a>
          val cmp = compare (elem, pivot)
          val () = current_sign := cmp
          prval () = fold@ lst
          val @(matches, rest) = list_vt_span<a> (pred, lst)
          val @(left, middle, right) =
            recurs (compare, pred, pivot, current_sign, rest)
        in
          if cmp < 0 then
            @(matches \append left, middle, right)
          else if cmp = 0 then
            @(left, matches \append middle, right)
          else
            @(left, middle, matches \append right)
        end 

    prval () = lemma_list_vt_param lst
    val retvals = recurs (compare, pred, pivot, current_sign, lst)

    val () = cloptr_free ($UN.castvwtp0{cloptr0} pred)
  in
    retvals
  end

(*------------------------------------------------------------------*)

fn {a : vt@ype}
three_way_partition_with_random_pivot
          {n       : nat}
          (compare : &((&a, &a) -<cloptr1> int),
           n       : int n,
           lst     : list_vt (a, n))
  : [n1, n2, n3 : nat | n1 + n2 + n3 == n]
    @(int n1, list_vt (a, n1),
      int n2, list_vt (a, n2),
      int n3, list_vt (a, n3)) =
let
  macdef append = list_vt_append<a>

  var pivot : a

  val randnum = random_double ()
  val i_pivot = $UN.cast{Size_t} (randnum * $UN.cast{double} n)
  prval () = lemma_g1uint_param i_pivot
  val () = assertloc (i_pivot < i2sz n)
  val i_pivot = sz2i i_pivot

  val @(left, right) = list_vt_split_at<a> (lst, i_pivot)
  val+ ~ (pivot_val :: right) = right
  val () = pivot := pivot_val

  val @(left1, middle1, right1) =
    list_vt_three_way_partition<a> (compare, pivot, left)
  val @(left2, middle2, right2) =
    list_vt_three_way_partition<a> (compare, pivot, right)

  val left = left1 \append left2
  val middle = middle1 \append (pivot :: middle2)
  val right = right1 \append right2

  val n1 = length<a> left
  val n2 = length<a> middle
  val n3 = n - n1 - n2
in
  @(n1, left, n2, middle, n3, right)
end

(*------------------------------------------------------------------*)

implement {a}
list_vt_three_way_separation {n, k} (compare, k, lst) =
  (* This is a quickselect with random pivot, returning a three-way
     partition, in which the middle partition contains the (k+1)st
     least element. *)
  let
    macdef append = list_vt_append<a>

    fun
    loop {n1, n2, n3, k : nat | 0 <= k; k < n;
                                n1 + n2 + n3 == n}
         (compare : &((&a, &a) -<cloptr1> int),
          k       : int k,
          n1      : int n1,
          left    : list_vt (a, n1),
          n2      : int n2,
          middle  : list_vt (a, n2),
          n3      : int n3,
          right   : list_vt (a, n3))
        : [n1, n2, n3 : nat | n1 + n2 + n3 == n;
                              n1 <= k; k < n1 + n2]
          @(int n1, list_vt (a, n1),
            int n2, list_vt (a, n2),
            int n3, list_vt (a, n3)) =
      if k < n1 then
        let
          val @(m1, left1, m2, middle1, m3, right1) =
            three_way_partition_with_random_pivot<a>
              (compare, n1, left)
        in
          loop (compare, k, m1, left1, m2, middle1,
                m3 + n2 + n3,
                right1 \append (middle \append right))
        end
      else if n1 + n2 <= k then
        let
          val @(m1, left2, m2, middle2, m3, right2) =
            three_way_partition_with_random_pivot<a>
              (compare, n3, right)
        in
          loop (compare, k, n1 + n2 + m1,
                left \append (middle \append left2),
                m2, middle2, m3, right2)
        end
      else
        @(n1, left, n2, middle, n3, right)

    prval () = lemma_list_vt_param lst

    val @(n1, left, n2, middle, n3, right) =
      three_way_partition_with_random_pivot<a>
        (compare, length<a> lst, lst)
  in
    loop (compare, k, n1, left, n2, middle, n3, right)
  end

(*------------------------------------------------------------------*)

implement {a}
list_vt_select_linear {n, k} (compare, k, lst) =
  (* This is a quickselect with random pivot. It is like
     list_vt_three_way_separation, but throws away parts of the list that
     will not be needed later on. *)
  let
    implement
    list_vt_freelin$clear<a> (x) =
      $effmask_all list_vt_select_linear$clear<a> (x)

    macdef append = list_vt_append<a>

    fun
    loop {n1, n2, n3, k : nat | 0 <= k; k < n1 + n2 + n3}
         (compare : &((&a, &a) -<cloptr1> int),
          k       : int k,
          n1      : int n1,
          left    : list_vt (a, n1),
          n2      : int n2,
          middle  : list_vt (a, n2),
          n3      : int n3,
          right   : list_vt (a, n3)) : a =
      if k < n1 then
        let
          val () = list_vt_freelin<a> middle
          val () = list_vt_freelin<a> right
          val @(m1, left1, m2, middle1, m3, right1) =
            three_way_partition_with_random_pivot<a>
              (compare, n1, left)
        in
          loop (compare, k, m1, left1, m2, middle1, m3, right1)
        end
      else if n1 + n2 <= k then
        let
          val () = list_vt_freelin<a> left
          val () = list_vt_freelin<a> middle
          val @(m1, left1, m2, middle1, m3, right1) =
            three_way_partition_with_random_pivot<a>
              (compare, n3, right)
        in
          loop (compare, k - n1 - n2,
                m1, left1, m2, middle1, m3, right1)
        end
      else
        let
          val () = list_vt_freelin<a> left
          val () = list_vt_freelin<a> right
          val @(middle1, middle2) =
            list_vt_split_at<a> (middle, k - n1)
          val () = list_vt_freelin<a> middle1
          val+ ~ (element :: middle2) = middle2
          val () = list_vt_freelin<a> middle2
        in
          element
        end

    prval () = lemma_list_vt_param lst

    val @(n1, left, n2, middle, n3, right) =
      three_way_partition_with_random_pivot<a>
        (compare, length<a> lst, lst)
  in
    loop (compare, k, n1, left, n2, middle, n3, right)
  end

implement {a}
list_vt_select {n, k} (compare, k, lst) =
  let
    implement
    list_vt_select_linear$clear<a> (x) = ()
  in
    list_vt_select_linear<a> {n, k} (compare, k, lst)
  end

(*------------------------------------------------------------------*)

implement {a}
list_vt_stable_sort {n} (compare, lst) =
  (* This is a stable quicksort with random pivot. *)
  let
    macdef append = list_vt_append<a>

    fun
    recurs {n          : int}
           {n1, n2, n3 : nat | n1 + n2 + n3 == n}
           (compare : &((&a, &a) -<cloptr1> int),
            n1      : int n1,
            left    : list_vt (a, n1),
            n2      : int n2,
            middle  : list_vt (a, n2),
            n3      : int n3,
            right   : list_vt (a, n3))
        : @(int n, list_vt (a, n)) =
      if 1 < n1 then
        let
          val @(m1, left1, m2, middle1, m3, right1) =
            three_way_partition_with_random_pivot<a>
              (compare, n1, left)
          val @(_, left) =
            recurs {n1} (compare, m1, left1, m2, middle1, m3, right1)
        in
          if 1 < n3 then
            let
              val @(m1, left1, m2, middle1, m3, right1) =
                three_way_partition_with_random_pivot<a>
                  (compare, n3, right)
              val @(_, right) =
                recurs {n3} (compare, m1, left1, m2, middle1,
                             m3, right1)
            in
              @(n1 + n2 + n3, left \append (middle \append right))
            end
          else
            @(n1 + n2 + n3, left \append (middle \append right))
        end
      else if 1 < n3 then
        let
           val @(m1, left1, m2, middle1, m3, right1) =
            three_way_partition_with_random_pivot<a>
              (compare, n3, right)
          val @(_, right) =
            recurs {n3} (compare, m1, left1, m2, middle1, m3, right1)
        in
          @(n1 + n2 + n3, left \append (middle \append right))
        end
      else
        @(n1 + n2 + n3, left \append (middle \append right))

    prval () = lemma_list_vt_param lst

    val @(n1, left, n2, middle, n3, right) =
      three_way_partition_with_random_pivot<a>
        (compare, length<a> lst, lst)
  in
    recurs {n} (compare, n1, left, n2, middle, n3, right)
  end

(*------------------------------------------------------------------*)

fn
print_kth (direction : int,
           k         : int,
           lst       : !List_vt int) : void =
  let
    var compare =
      lam (x : &int, y : &int) : int =<cloptr1>
        if x < y then
          ~direction
        else if x = y then
          0
        else
          direction

    val lst = copy<int> lst
    val n = length<int> lst
    val k = g1ofg0 k
    val () = assertloc (1 <= k)
    val () = assertloc (k <= n)
    val element = list_vt_select<int> (compare, k - 1, lst)

    val () = cloptr_free ($UN.castvwtp0{cloptr0} compare)
  in
    print! (element)
  end

fn
demonstrate_quickselect () : void =
  let
    var example_for_select = $list_vt (9, 8, 7, 6, 5, 0, 1, 2, 3, 4)

    val () = print! ("With < as order predicate:  ")
    val () = print_kth (1, 1, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 2, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 3, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 4, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 5, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 6, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 7, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 8, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 9, example_for_select)
    val () = print! (" ")
    val () = print_kth (1, 10, example_for_select)
    val () = println! ()

    val () = print! ("With > as order predicate:  ")
    val () = print_kth (~1, 1, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 2, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 3, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 4, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 5, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 6, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 7, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 8, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 9, example_for_select)
    val () = print! (" ")
    val () = print_kth (~1, 10, example_for_select)
    val () = println! ()

    val () = list_vt_free<int> example_for_select
  in
  end

fn
demonstrate_quicksort () : void =
  let
    var example_for_sort =
      $list_vt ("elephant", "duck", "giraffe", "deer",
                "earwig", "dolphin", "wildebeest", "pronghorn",
                "woodlouse", "whip-poor-will")

    var compare =
      lam (x : &stringGt 0,
           y : &stringGt 0) : int =<cloptr1>
        if x[0] < y[0] then
          ~1
        else if x[0] = y[0] then
          0
        else
          1

    val () = println! ("stable sort by first character:")
    val @(_, sorted_lst) =
      list_vt_stable_sort<stringGt 0>
        (compare, copy<stringGt 0> example_for_sort)
    val () = println! ($UN.castvwtp1{List0 string} sorted_lst)
  in
    list_vt_free<string> sorted_lst;
    list_vt_free<string> example_for_sort;
    cloptr_free ($UN.castvwtp0{cloptr0} compare)
  end

implement
main0 (argc, argv) =
  let

    (* Currently there is no demonstration of
       list_vt_three_way_separation. *)

    val demo_name =
      begin
        if 2 <= argc then
          $UN.cast{string} argv[1]
        else
          begin
            println!
              ("Please choose \"quickselect\" or \"quicksort\".");
            exit (1)
          end
      end : string

  in

    if demo_name = "quickselect" then
      demonstrate_quickselect ()
    else if demo_name = "quicksort" then
      demonstrate_quicksort ()
    else
      begin
        println! ("Please choose \"quickselect\" or \"quicksort\".");
        exit (1)
      end

  end

(*------------------------------------------------------------------*)
Output:
$ patscc -O3 -DATS_MEMALLOC_LIBC quickselect_task_for_list_vt.dats && ./a.out quickselect
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

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 

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

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 >

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

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
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:

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.

Common Lisp

Translation of: Haskell
(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)))
Output:
(0 1 2 3 4 5 6 7 8 9)

Crystal

Translation of: 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
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

D

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 

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]

Delphi

Translation of: Go
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.

EasyLang

proc qselect k . list[] res .
   # 
   subr partition
      mid = left
      for i = left + 1 to right
         if list[i] < list[left]
            mid += 1
            swap list[i] list[mid]
         .
      .
      swap list[left] list[mid]
   .
   left = 1
   right = len list[]
   while left < right
      partition
      if mid < k
         left = mid + 1
      elif mid > k
         right = mid - 1
      else
         left = right
      .
   .
   res = list[k]
.
d[] = [ 9 8 7 6 5 0 1 2 3 4 ]
for i = 1 to len d[]
   qselect i d[] r
   print r
.

Elixir

Translation of: Erlang
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
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Erlang

Translation of: Haskell
-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.

Output:

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

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]

Factor

Translation of: Haskell
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
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...
      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.
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.

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
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

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

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])
Output:
[0,1,2,3,4,5,6,7,8,9]

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 
->

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.)

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

JavaScript

ES5

// 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);
  }
}

Example:

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) });
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

ES6

Translation of: Haskell
(() => {
    '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));
})();
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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
$

Julia

Using builtin function partialsort:

v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
@show v partialsort(v, 1:10)
Output:
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
partialsort(v, 1:10) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Kotlin

// 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()
}
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

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
Output:
1       0
2       1
3       2
4       3
5       4
6       5
7       6
8       7
9       8
10      9

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)):
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

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]
Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Mercury

Works with: Mercury version 22.01.1


%%%-------------------------------------------------------------------

:- 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:
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

/* 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

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)

Output:

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

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|]

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)
  )
};

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

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

Picat

From the Wikipedia algorithm.

main =>
  L = [9,8,7,6,5,0,1,2,3,4],
  Len = L.len,
  println([select(L,1,Len,I) : I in 1..Len]),
  nl.

select(List, Left, Right, K) = Select =>
  if Left = Right then
    Select = List[Left]
  else 
    PivotIndex  = partition(List, Left, Right, random(Left,Right)),
    if K == PivotIndex then
      Select = List[K]
    elseif K < PivotIndex then
      Select = select(List, Left, PivotIndex-1, K)
    else
      Select = select(List, PivotIndex+1, Right, K)
    end
  end.

partition(List, Left, Right, PivotIndex) = StoreIndex =>
  PivotValue = List[PivotIndex],
  swap(List,PivotIndex,Right),
  StoreIndex = Left,
  foreach(I in Left..Right-1)
    if List[I] @< PivotValue then
      swap(List,StoreIndex,I),
      StoreIndex := StoreIndex+1
    end
  end,
  swap(List,Right,StoreIndex).

% swap L[I] <=> L[J]
swap(L,I,J) => 
  T = L[I],
  L[I] := L[J],
  L[J] := T.
Output:
[0,1,2,3,4,5,6,7,8,9]

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) ) ) )
Output:
(0 1 2 3 4 5 6 7 8 9)

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

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)"

Output:

0 1 2 3 4 5 6 7 8 9

PureBasic

A direct implementation of the Wikipedia pseudo-code.

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
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.

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]

Composition of pure functions

Translation of: Haskell
Works with: Python version 3
'''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()
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

Raku

(formerly Perl 6)

Translation of: Python
Works with: rakudo version 2015-10-20
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;
            }
        }
    }
}
Output:
0 1 2 3 4 5 6 7 8 9

REXX

uses in-line swap

/*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*/
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

/*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.*/
output   is the identical to the 1st REXX version.


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

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]

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]);
    }
}
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

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

Scheme

Translation of: Mercury
Works with: Gauche Scheme version 0.9.11-p1
Works with: Chibi Scheme version 0.10.0 "neon"


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.

;;
;; 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 order predicate: ")
(do ((k 1 (+ k 1)))
    ((= k 11))
  (print-kth < k example-numbers))
(newline)
(display "With > as order predicate: ")
(do ((k 1 (+ k 1)))
    ((= k 11))
  (print-kth > k example-numbers))
(newline)
Output:
$ gosh quickselect_task.scm
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

Sidef

func quickselect(a, k) {
    var pivot = a.pick
    var left  = a.grep{|i| i < pivot}
    var right = a.grep{|i| i > pivot}

    given(left.len) { |l|
        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)}
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

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

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

VBA

Translation of: Phix
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
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Wren

Library: Wren-sort

The Find.quick method in the above module implements the quickselect algorithm.

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()
Output:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

XPL0

Translation of: Go
func QuickSelect(List, Len, K);
int  List, Len, K;
int  Px, Pv, Last, I, J, T;
[loop   [\\partition
        Px:= Len/2;
        Pv:= List(Px);
        Last:= Len-1;
        T:= List(Px);  List(Px):= List(Last);  List(Last):= T;
        I:= 0;
        for J:= 0 to Last-1 do
            [if List(J) < Pv then
                [T:= List(I);  List(I):= List(J);  List(J):= T;
                I:= I+1;
                ];
            ];
        \\select
        if I = K then return Pv;

        if K < I then Len:= I
        else    [T:= List(I);  List(I):= List(Last);  List(Last):= T;
                List:= @List(I+1);
                Len:= Last - I;
                K:= K - (I+1);
                ];
        ];
];

int V, K;
[V:= [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
for K:= 0 to 10-1 do
    [IntOut(0, QuickSelect(V, 10, K));
    ChOut(0, ^ );
    ];
]
Output:
0 1 2 3 4 5 6 7 8 9 

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