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.

Java

<lang java>import java.util.Random;

public class QuickSelect {

private static int partition(int[] arr, int left, int right, int pivot) { int pivotVal = arr[pivot]; swap(arr, pivot, right); int storeIndex = left; for (int i = left; i < right; i++) { if (arr[i] < pivotVal) { swap(arr, i, storeIndex); storeIndex++; } } swap(arr, right, storeIndex); return storeIndex; }

private static int select(int[] 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 - left == n) { right = left = pivotIndex; } else if (pivotIndex - left < n) { n -= pivotIndex - left + 1; left = pivotIndex + 1; } else { right = pivotIndex - 1; } } return arr[left]; }

private static void swap(int[] arr, int i1, int i2) { if (i1 != i2) { int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } }

public static void main(String[] args) { int[] input = new int[]{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}; for (int i = 0; i < 10; i++) { System.out.print(select(input, i)); if (i < 9) System.out.print(", "); } }

}</lang>

Output:

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

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]

Tcl

Translation of: Python

<lang tcl># Swap the values at two indices of a list proc swap {list i j} {

   upvar 1 $list l
   set tmp [lindex $l $i]
   lset l $i [lindex $l $j]
   lset l $j $tmp

}

proc quickselect {vector k {left 0} {right ""}} {

   set last [expr {[llength $vector] - 1}]
   if {$right eq ""} {

set right $last

   }
   # Sanity assertions
   if {![llength $vector] || $k <= 0} {

error "Either empty vector, or k <= 0"

   } elseif {![tcl::mathop::<= 0 $left $last]} {

error "left is out of range"

   } elseif {![tcl::mathop::<= $left $right $last]} {

error "right is out of range"

   }

   # the _select core, inlined
   while 1 {

set pivotIndex [expr {int(rand()*($right-$left))+$left}]

# the partition core, inlined set pivotValue [lindex $vector $pivotIndex] swap vector $pivotIndex $right set storeIndex $left for {set i $left} {$i <= $right} {incr i} { if {[lindex $vector $i] < $pivotValue} { swap vector $storeIndex $i incr storeIndex } } swap vector $right $storeIndex set pivotNewIndex $storeIndex

set pivotDist [expr {$pivotNewIndex - $left + 1}] if {$pivotDist == $k} { return [lindex $vector $pivotNewIndex] } elseif {$k < $pivotDist} { set right [expr {$pivotNewIndex - 1}] } else { set k [expr {$k - $pivotDist}] set left [expr {$pivotNewIndex + 1}] }

   }

}</lang> Demonstrating: <lang tcl>set v {9 8 7 6 5 0 1 2 3 4} foreach i {1 2 3 4 5 6 7 8 9 10} {

   puts "$i => [quickselect $v $i]"

}</lang>

Output:

1 => 0
2 => 1
3 => 2
4 => 3
5 => 4
6 => 5
7 => 6
8 => 7
9 => 8
10 => 9