Quickselect algorithm

Quickselect algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

Perl 6

Translation of: Python

<lang Perl 6>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, $left is copy, $right is copy, $k is copy where $k >= 1) {

   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;
       if $pivot-dist == $k {
           return @vector[$pivot-new-index];
       }
       elsif $k < $pivot-dist {
           $right = $pivot-new-index - 1;
       }
       else {
           $k -= $pivot-dist;
           $left = $pivot-new-index + 1;
       }
   }

}

sub select(@vector, $k, $left = 0, $right? is copy) {

   $right //= @vector.end;
   @vector and $k > 0 or die "Either null vector or k <= 0 ";
   0 <= $left <= @vector or die "left is out of range";
   $left <= $right <= @vector or die "right is out of range";
   _select(@vector, $left, $right, $k);

}</lang>

Output:

0 1 2 3 4 5 6 7 8 9

Python

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

def partition(vector, left, right, pivotIndex):

   pivotValue = vector[pivotIndex]
   vector[pivotIndex], vector[right] = vector[right], vector[pivotIndex]  # Move pivot to end
   storeIndex = left
   for i in range(left, right):
       if vector[i] < pivotValue:
           vector[storeIndex], vector[i] = vector[i], vector[storeIndex]
           storeIndex += 1
   vector[right], vector[storeIndex] = vector[storeIndex], vector[right]  # Move pivot to its final place
   return storeIndex

def _select(vector, left, right, k):

   "Returns the k-th smallest, (k >= 1), 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 + 1
       if pivotDist == k:
           return vector[pivotNewIndex]
       elif k < pivotDist:
           right = pivotNewIndex - 1
       else:
           k = k - pivotDist
           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 ommitted
   """
   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+1) for i in range(10)])</lang> 

Output:

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