Quickselect algorithm

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.

C++

Library

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

1. include <iostream>

int main() {

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

 return 0;

}</lang>

Output:

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

Implementation

A more explicit implementation: <lang cpp>#include <iterator>

1. include <algorithm>
2. include <functional>
3. include <cstdlib>
4. include <ctime>
5. include <iostream>

template <typename Iterator> Iterator select(Iterator begin, Iterator end, int n) {

 typedef typename std::iterator_traits<Iterator>::value_type T;
 while (true) {
   Iterator pivotIt = begin + std::rand() % std::distance(begin, end);
   std::iter_swap(pivotIt, end-1);  // Move pivot to end
   pivotIt = std::partition(begin, end-1, std::bind2nd(std::less<T>(), *(end-1)));
   std::iter_swap(end-1, pivotIt);  // Move pivot to its final place
   if (n == pivotIt - begin) {
     return pivotIt;
   } else if (n < pivotIt - begin) {
     end = pivotIt;
   } else {
     n -= pivotIt+1 - begin;
     begin = pivotIt+1;
   }
 }

}

int main() {

 std::srand(std::time(NULL));
 for (int i = 0; i < 10; i++) {
   int a[] = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
   std::cout << *select(a, a + sizeof(a)/sizeof(*a), i);
   if (i < 9) std::cout << ", ";
 }
 std::cout << std::endl;

 return 0;

}</lang>

Output:

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

C#

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

<lang csharp>// ---------------------------------------------------------------------------------------------- // // Program.cs - QuickSelect // // ----------------------------------------------------------------------------------------------

using System; using System.Collections.Generic; using System.Linq;

namespace QuickSelect {

   internal static class Program
   {
       #region Static Members

       private static void Main()
       {
           var inputArray = new[] {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
           // Loop 10 times
           Console.WriteLine( "Loop quick select 10 times." );
           for( var i = 0 ; i < 10 ; i++ )
           {
               Console.Write( inputArray.NthSmallestElement( i ) );
               if( i < 9 )
                   Console.Write( ", " );
           }
           Console.WriteLine();

           // And here is then more effective way to get N smallest elements from vector in order by using quick select algorithm
           // Basically we are here just sorting array (taking 10 smallest from array which length is 10)
           Console.WriteLine( "Just sort 10 elements." );
           Console.WriteLine( string.Join( ", ", inputArray.TakeSmallest( 10 ).OrderBy( v => v ).Select( v => v.ToString() ).ToArray() ) );
           // Here we are actually doing quick select once by taking only 4 smallest from array. 
           Console.WriteLine( "Get 4 smallest and sort them." );
           Console.WriteLine( string.Join( ", ", inputArray.TakeSmallest( 4 ).OrderBy( v => v ).Select( v => v.ToString() ).ToArray() ) );
           Console.WriteLine( "< Press any key >" );
           Console.ReadKey();
       }

       #endregion
   }

   internal static class ArrayExtension
   {
       #region Static Members

       /// <summary>
       ///  Return specified number of smallest elements from array.
       /// </summary>
       /// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
       /// <param name="array">The array to return elemnts from.</param>
       /// <param name="count">The number of smallest elements to return. </param>
       /// <returns>An IEnumerable(T) that contains the specified number of smallest elements of the input array. Returned elements are NOT sorted.</returns>
       public static IEnumerable<T> TakeSmallest<T>( this T[] array, int count ) where T : IComparable<T>
       {
           if( count < 0 )
               throw new ArgumentOutOfRangeException( "count", "Count is smaller than 0." );
           if( count == 0 )
               return new T[0];
           if( array.Length <= count )
               return array;

           return QuickSelectSmallest( array, count - 1 ).Take( count );
       }

       /// <summary>
       /// Returns N:th smallest element from the array.
       /// </summary>
       /// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
       /// <param name="array">The array to return elemnt from.</param>
       /// <param name="n">Nth element. 0 is smallest element, when array.Length - 1 is largest element.</param>
       /// <returns>N:th smalles element from the array.</returns>
       public static T NthSmallestElement<T>( this T[] array, int n ) where T : IComparable<T>
       {
           if( n < 0 || n > array.Length - 1 )
               throw new ArgumentOutOfRangeException( "n", n, string.Format( "n should be between 0 and {0} it was {1}.", array.Length - 1, n ) );
           if( array.Length == 0 )
               throw new ArgumentException( "Array is empty.", "array" );
           if( array.Length == 1 )
               return array[ 0 ];

           return QuickSelectSmallest( array, n )[ n ];
       }

       /// <summary>
       ///  Partially sort array such way that elements before index position n are smaller or equal than elemnt at position n. And elements after n are larger or equal. 
       /// </summary>
       /// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
       /// <param name="input">The array which elements are being partially sorted. This array is not modified.</param>
       /// <param name="n">Nth smallest element.</param>
       /// <returns>Partially sorted array.</returns>
       private static T[] QuickSelectSmallest<T>( T[] input, int n ) where T : IComparable<T>
       {
           // Let's not mess up with our input array
           // For very large arrays - we should optimize this somehow - or just mess up with our input
           var partiallySortedArray = (T[]) input.Clone();
          
           // Initially we are going to execute quick select to entire array
           var startIndex = 0;
           var endIndex = input.Length - 1;
           
           // Selecting initial pivot
           // Maybe we are lucky and array is sorted initially?
           var pivotIndex = n;

           // Loop until there is nothing to loop (this actually shouldn't happen - we should find our value before we run out of values)
           var r = new Random();
           while( endIndex > startIndex )
           {
               pivotIndex = QuickSelectPartition( partiallySortedArray, startIndex, endIndex, pivotIndex );
               if( pivotIndex == n )
                   // We found our n:th smallest value - it is stored to pivot index
                   break;
               if( pivotIndex > n )
                   // Array before our pivot index have more elements that we are looking for                    
                   endIndex = pivotIndex - 1;
               else                    
                   // Array before our pivot index has less elements that we are looking for                    
                   startIndex = pivotIndex + 1;

               // Omnipotent beings don't need to roll dices - but we do...
               // Randomly select a new pivot index between end and start indexes (there are other methods, this is just most brutal and simplest)
               pivotIndex = r.Next( startIndex,  endIndex );
           }
           return partiallySortedArray;
       }

       /// <summary>
       /// Sort elements in sub array between startIndex and endIndex, such way that elements smaller than or equal with value initially stored to pivot index are before
       /// new returned pivot value index.
       /// </summary>
       /// <typeparam name="T">The type of the elements of array. Type must implement IComparable(T) interface.</typeparam>
       /// <param name="array">The array that is being sorted.</param>
       /// <param name="startIndex">Start index of sub array.</param>
       /// <param name="endIndex">End index of sub array.</param>
       /// <param name="pivotIndex">Pivot index.</param>
       /// <returns>New pivot index. Value that was initially stored to <paramref name="pivotIndex"/> is stored to this newly returned index. All elements before this index are 
       /// either smaller or equal with pivot value. All elements after this index are larger than pivot value.</returns>
       /// <remarks>This method modifies paremater array.</remarks>
       private static int QuickSelectPartition<T>( this T[] array, int startIndex, int endIndex, int pivotIndex ) where T : IComparable<T>
       {
           var pivotValue = array[ pivotIndex ];
           // Initially we just assume that value in pivot index is largest - so we move it to end (makes also for loop more straight forward)
           array.Swap( pivotIndex, endIndex );
           for( var i = startIndex ; i < endIndex ; i++ )
           {
               if( array[ i ].CompareTo( pivotValue ) > 0 )
                   continue;

               // Value stored to i was smaller than or equal with pivot value - let's move it to start
               array.Swap( i, startIndex );
               // Move start one index forward 
               startIndex++;
           }
           // Start index is now pointing to index where we should store our pivot value from end of array
           array.Swap( endIndex, startIndex );
           return startIndex;
       }

       private static void Swap<T>( this T[] array, int index1, int index2 )
       {
           if( index1 == index2 )
               return;

           var temp = array[ index1 ];
           array[ index1 ] = array[ index2 ];
           array[ index2 ] = temp;
       }

       #endregion
   }

}</lang>

Output:

Loop quick select 10 times.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Just sort 10 elements.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Get 4 smallest and sort them.
0, 1, 2, 3
< Press any key >

D

Standard Version

This could use a different algorithm: <lang d>void main() {

   import std.stdio, std.algorithm;

   auto a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
   foreach (immutable i; 0 .. a.length) {
       a.topN(i);
       write(a[i], " ");
   }

}</lang>

Output:

0 1 2 3 4 5 6 7 8 9 

Array Version

Translation of: Java

<lang d>import std.stdio, std.random, std.algorithm, std.range;

T quickSelect(T)(T[] arr, size_t n) in {

   assert(n < arr.length);

} body {

   static size_t partition(T[] sub, in size_t pivot) pure nothrow
   in {
       assert(!sub.empty);
       assert(pivot < sub.length);
   } body {
       auto pivotVal = sub[pivot];
       sub[pivot].swap(sub.back);
       size_t storeIndex = 0;
       foreach (ref si; sub[0 .. $ - 1]) {
           if (si < pivotVal) {
               si.swap(sub[storeIndex]);
               storeIndex++;
           }
       }
       sub.back.swap(sub[storeIndex]);
       return storeIndex;
   }

   size_t left = 0;
   size_t right = arr.length - 1;
   while (right > left) {
       assert(left < arr.length);
       assert(right < arr.length);
       immutable pivotIndex = left + partition(arr[left .. right + 1],
           uniform(0U, right - left + 1));
       if (pivotIndex - left == n) {
           right = left = pivotIndex;
       } else if (pivotIndex - left < n) {
           n -= pivotIndex - left + 1;
           left = pivotIndex + 1;
       } else {
           right = pivotIndex - 1;
       }
   }

   return arr[left];

}

void main() {

   auto a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
   a.length.iota.map!(i => a.quickSelect(i)).writeln;

}</lang>

Output:

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

F#

Translation of: Haskell

<lang fsharp> let rec quickselect k list =

   match list with
   | [] -> failwith "Cannot take largest element of empty list."
   | [a] -> a
   | x::xs ->
       let (ys, zs) = List.partition (fun arg -> arg < x) xs
       let l = List.length ys
       if k < l then quickselect k ys
       elif k > l then quickselect (k-l-1) zs
       else x

//end quickselect

[<EntryPoint>] let main args =

   let v = [9; 8; 7; 6; 5; 0; 1; 2; 3; 4]
   printfn "%A" [for i in 0..(List.length v - 1) -> quickselect i v]
   0

</lang>

Output:

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

Haskell

<lang haskell>import Data.List (partition)

quickselect :: Ord a => Int -> [a] -> a quickselect k (x:xs) | k < l = quickselect k ys

                    | k > l     = quickselect (k-l-1) zs
                    | otherwise = x
 where (ys, zs) = partition (< x) xs
       l = length ys

main :: IO () main = do

 let v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
 print $ map (\i -> quickselect i v) [0 .. length v-1]</lang>

Output:

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

Java

<lang java>import java.util.Random;

public class QuickSelect {

private static <E extends Comparable<? super E>> int partition(E[] arr, int left, int right, int pivot) { E pivotVal = arr[pivot]; swap(arr, pivot, right); int storeIndex = left; for (int i = left; i < right; i++) { if (arr[i].compareTo(pivotVal) < 0) { swap(arr, i, storeIndex); storeIndex++; } } swap(arr, right, storeIndex); return storeIndex; }

private static <E extends Comparable<? super E>> E select(E[] arr, int n) { int left = 0; int right = arr.length - 1; Random rand = new Random(); while (right > left) { int pivotIndex = partition(arr, left, right, rand.nextInt(right - left + 1) + left); if (pivotIndex - 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(Object[] arr, int i1, int i2) { if (i1 != i2) { Object temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } }

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

}</lang>

Output:

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

OCaml

<lang ocaml>let rec quickselect k = function

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

Usage:

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

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,

           \k where 1 .. @vector,
           \l where 0 .. @vector = 0,
           \r where l .. @vector = @vector.end ) {

   my ($k, $left, $right) = k, l, r;

   loop {
       my $pivot-index = ($left..$right).pick;
       my $pivot-new-index = partition(@vector, $left, $right, $pivot-index);
       my $pivot-dist = $pivot-new-index - $left + 1;
       given $pivot-dist <=> $k {
           when Same {
               return @vector[$pivot-new-index];
           }
           when Decrease {
               $right = $pivot-new-index - 1;
           }
           when Increase {
               $k -= $pivot-dist;
               $left = $pivot-new-index + 1;
           }
       }
   }

}</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 >= 0), element of vector within vector[left:right+1] inclusive."
   while True:
       pivotIndex = random.randint(left, right)     # select pivotIndex between left and right
       pivotNewIndex = partition(vector, left, right, pivotIndex)
       pivotDist = pivotNewIndex - left
       if pivotDist == k:
           return vector[pivotNewIndex]
       elif k < pivotDist:
           right = pivotNewIndex - 1
       else:
           k -= pivotDist + 1
           left = pivotNewIndex + 1

def select(vector, k, left=None, right=None):

   """\
   Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1].
   left, right default to (0, len(vector) - 1) if omitted
   """
   if left is None:
       left = 0
   lv1 = len(vector) - 1
   if right is None:
       right = lv1
   assert vector and k >= 0, "Either null vector or k < 0 "
   assert 0 <= left <= lv1, "left is out of range"
   assert left <= right <= lv1, "right is out of range"
   return _select(vector, left, right, k)

if __name__ == '__main__':

   v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
   print([select(v, i) for i in range(10)])</lang> 

Output:

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

Racket

<lang racket>(define (quickselect A k)

 (define pivot (list-ref A (random (length A))))
 (define A1 (filter (curry > pivot) A))
 (define A2 (filter (curry < pivot) A))
 (cond
   [(<= k (length A1)) (quickselect A1 k)]
   [(> k (- (length A) (length A2))) (quickselect A2 (- k (- (length A) (length A2))))]
   [else pivot]))

(define a '(9 8 7 6 5 0 1 2 3 4)) (display (string-join (map number->string (for/list ([k 10]) (quickselect a (+ 1 k)))) ", ")) </lang>

Output:

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

Standard ML

<lang sml>fun quickselect (_, _, []) = raise Fail "empty"

 | quickselect (k, cmp, x :: xs) = let
       val (ys, zs) = List.partition (fn y => cmp (y, x) = LESS) xs
       val l = length ys
     in
       if k < l then
         quickselect (k, cmp, ys)
       else if k > l then
         quickselect (k-l-1, cmp, zs)
       else
         x
     end</lang>

Usage:

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

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