Quickselect algorithm: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Go}}: added another version)
Line 535: Line 535:
}
}
fmt.Println(quickselect(v, i))
fmt.Println(quickselect(v, i))
}
}</lang>
{{out}}
<pre>
0
1
2
3
4
5
6
7
8
9
</pre>

A more generic version that works for any container that conforms to <code>sort.Interface</code>:

<lang go>package main

import (
"fmt"
"sort"
"math/rand"
)

func partition(a sort.Interface, first int, last int, pivotIndex int) int {
a.Swap(first, pivotIndex) // move it to beginning
left := first+1
right := last
for left <= right {
for left <= last && a.Less(left, first) {
left++
}
for right >= first && a.Less(first, right) {
right--
}
if left <= right {
a.Swap(left, right)
left++
right--
}
}
a.Swap(first, right) // swap into right place
return right
}

func quickselect(a sort.Interface, n int) int {
first := 0
last := a.Len()-1
for {
pivotIndex := partition(a, first, last,
rand.Intn(last - first + 1) + first)
if n == pivotIndex {
return pivotIndex
} else if n < pivotIndex {
last = pivotIndex-1
} else {
first = pivotIndex+1
}
}
panic("bad index")
}

func main() {
for i := 0; ; i++ {
v := []int{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
if i == len(v) {
return
}
fmt.Println(v[quickselect(sort.IntSlice(v), i)])
}
}
}</lang>
}</lang>

Revision as of 09:00, 24 February 2014

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.

AutoHotkey

Works with: AutoHotkey_L

(AutoHotkey1.1+)

A direct implementation of the Wikipedia pseudo-code. <lang AutoHotkey>MyList := [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] Loop, 10 Out .= Select(MyList, 1, MyList.MaxIndex(), A_Index) (A_Index = MyList.MaxIndex() ? "" : ", ") MsgBox, % Out return

Partition(List, Left, Right, PivotIndex) { PivotValue := List[PivotIndex] , Swap(List, pivotIndex, Right) , StoreIndex := Left , i := Left - 1 Loop, % Right - Left if (List[j := i + A_Index] <= PivotValue) Swap(List, StoreIndex, j) , StoreIndex++ Swap(List, Right, StoreIndex) return StoreIndex }

Select(List, Left, Right, n) { if (Left = Right) return List[Left] Loop { PivotIndex := (Left + Right) // 2 , PivotIndex := Partition(List, Left, Right, PivotIndex) if (n = PivotIndex) return List[n] else if (n < PivotIndex) Right := PivotIndex - 1 else Left := PivotIndex + 1 } }

Swap(List, i1, i2) { t := List[i1] , List[i1] := List[i2] , List[i2] := t }</lang> Output: 

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

C++

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 >

COBOL

The following is in the Managed COBOL dialect:

Works with: Visual COBOL

<lang cobol> CLASS-ID MainProgram. 

      METHOD-ID Partition STATIC USING T.
      CONSTRAINTS.
          CONSTRAIN T IMPLEMENTS type IComparable.
          
      DATA DIVISION.
      LOCAL-STORAGE SECTION.
      01  pivot-val              T.
      
      PROCEDURE DIVISION USING VALUE arr AS T OCCURS ANY,
              left-idx AS BINARY-LONG, right-idx AS BINARY-LONG,
              pivot-idx AS BINARY-LONG
              RETURNING ret AS BINARY-LONG.
          MOVE arr (pivot-idx) TO pivot-val
          INVOKE self::Swap(arr, pivot-idx, right-idx)
          DECLARE store-idx AS BINARY-LONG = left-idx
          PERFORM VARYING i AS BINARY-LONG FROM left-idx BY 1
                  UNTIL i > right-idx
              IF arr (i) < pivot-val
                  INVOKE self::Swap(arr, i, store-idx)
                  ADD 1 TO store-idx
              END-IF
          END-PERFORM
          INVOKE self::Swap(arr, right-idx, store-idx)
          
          MOVE store-idx TO ret
      END METHOD.
      
      METHOD-ID Quickselect STATIC USING T.
      CONSTRAINTS.
          CONSTRAIN T IMPLEMENTS type IComparable.
          
      PROCEDURE DIVISION USING VALUE arr AS T OCCURS ANY,
              left-idx AS BINARY-LONG, right-idx AS BINARY-LONG,
              n AS BINARY-LONG
              RETURNING ret AS T.
          IF left-idx = right-idx
              MOVE arr (left-idx) TO ret
              GOBACK
          END-IF
      
          DECLARE rand AS TYPE Random = NEW Random()
          DECLARE pivot-idx AS BINARY-LONG = rand::Next(left-idx, right-idx)
          DECLARE pivot-new-idx AS BINARY-LONG
              = self::Partition(arr, left-idx, right-idx, pivot-idx)
          DECLARE pivot-dist AS BINARY-LONG = pivot-new-idx - left-idx + 1
          
          EVALUATE TRUE
              WHEN pivot-dist = n
                  MOVE arr (pivot-new-idx) TO ret                   
                     
              WHEN n < pivot-dist
                  INVOKE self::Quickselect(arr, left-idx, pivot-new-idx - 1, n)
                      RETURNING ret
                    
              WHEN OTHER
                  INVOKE self::Quickselect(arr, pivot-new-idx + 1, right-idx,
                      n - pivot-dist) RETURNING ret
          END-EVALUATE
      END METHOD.
      
      METHOD-ID Swap STATIC USING T.
      CONSTRAINTS.
          CONSTRAIN T IMPLEMENTS type IComparable.
          
      DATA DIVISION.
      LOCAL-STORAGE SECTION.
      01  temp                   T.
          
      PROCEDURE DIVISION USING arr AS T OCCURS ANY,
              VALUE idx-1 AS BINARY-LONG, idx-2 AS BINARY-LONG.
          IF idx-1 <> idx-2
              MOVE arr (idx-1) TO temp
              MOVE arr (idx-2) TO arr (idx-1)
              MOVE temp TO arr (idx-2)
          END-IF
      END METHOD.
      
      METHOD-ID Main STATIC.
      PROCEDURE DIVISION.
          DECLARE input-array AS BINARY-LONG OCCURS ANY
              = TABLE OF BINARY-LONG(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
          DISPLAY "Loop quick select 10 times."
          PERFORM VARYING i AS BINARY-LONG FROM 1 BY 1 UNTIL i > 10
              DISPLAY self::Quickselect(input-array, 1, input-array::Length, i)
                  NO ADVANCING
              
              IF i < 10
                  DISPLAY ", " NO ADVANCING
              END-IF
          END-PERFORM
          DISPLAY SPACE
      END METHOD.
      END CLASS.</lang>

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]

Go

<lang go>package main

import "fmt"

func quickselect(list []int, k int) int { 

   for {
       // partition
       px := len(list) / 2
       pv := list[px]
       last := len(list) - 1
       list[px], list[last] = list[last], list[px]
       i := 0
       for j := 0; j < last; j++ {
           if list[j] < pv {
               list[i], list[j] = list[j], list[i]
               i++
           }
       }
       // select
       if i == k {
           return pv
       }
       if k < i {
           list = list[:i]
       } else {
           list[i], list[last] = list[last], list[i]
           list = list[i+1:]
           k -= i + 1
       }
   }

}

func main() { 

   for i := 0; ; i++ {
       v := []int{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
       if i == len(v) {
           return
       }
       fmt.Println(quickselect(v, i))
   }

}</lang>

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

A more generic version that works for any container that conforms to sort.Interface:

<lang go>package main

import ( 

   "fmt"
   "sort"
   "math/rand"

)

func partition(a sort.Interface, first int, last int, pivotIndex int) int { 

   a.Swap(first, pivotIndex) // move it to beginning
   left := first+1
   right := last
   for left <= right {
       for left <= last && a.Less(left, first) {
           left++
       }
       for right >= first && a.Less(first, right) {
           right--
       }
       if left <= right {
           a.Swap(left, right)
           left++
           right--
       }
   }
   a.Swap(first, right) // swap into right place
   return right

}

func quickselect(a sort.Interface, n int) int { 

   first := 0
   last := a.Len()-1
   for {
       pivotIndex := partition(a, first, last,

rand.Intn(last - first + 1) + first) 

       if n == pivotIndex {
           return pivotIndex
       } else if n < pivotIndex {
           last = pivotIndex-1
       } else {
           first = pivotIndex+1
       }
   }
   panic("bad index")

}

func main() { 

   for i := 0; ; i++ {
       v := []int{9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
       if i == len(v) {
           return
       }
       fmt.Println(v[quickselect(sort.IntSlice(v), i)])
   }

}</lang>

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

Haskell

<lang haskell>import Data.List (partition)

quickselect :: Ord a => 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]

Icon and Unicon

The following works in both languages. <lang unicon>procedure main(A) 

   every writes(" ",select(1 to *A, A, 1, *A)|"\n")

end

procedure select(k,A,min,max) 

   repeat {
       pNI := partition(?(max-min)+min, A, min, max)
       pD := pNI - min + 1
       if pD = k then return A[pNI]
       if k < pD then max := pNI-1
       else (k -:= pD, min := pNI+1)
       }

end

procedure partition(pivot,A,min,max) 

   pV := (A[max] :=: A[pivot])
   sI := min
   every A[i := min to max-1] <= pV do (A[sI] :=: A[i], sI +:= 1)
   A[max] :=: A[sI]
   return sI

end</lang>

Sample run: 

->qs 9 8 7 6 5 0 1 2 3 4
 0 1 2 3 4 5 6 7 8 9 
->

Java

<lang java>import java.util.Random;

public class QuickSelect {

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

private static <E extends Comparable<? super E>> E select(E[] arr, int n) { int left = 0; int right = arr.length - 1; Random rand = new Random(); while (right >= left) { int pivotIndex = partition(arr, left, right, rand.nextInt(right - left + 1) + left); if (pivotIndex == n) { return arr[pivotIndex]; } else if (pivotIndex < n) { left = pivotIndex + 1; } else { right = pivotIndex - 1; } } return null; }

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

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

}</lang>

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

NetRexx

<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary /** @see <a href="http://en.wikipedia.org/wiki/Quickselect">http://en.wikipedia.org/wiki/Quickselect</a> */

runSample(arg) return

-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ method qpartition(list, ileft, iright, pivotIndex) private static 

 pivotValue = list[pivotIndex]
 list = swap(list, pivotIndex, iright) -- Move pivot to end
 storeIndex = ileft
 loop i_ = ileft to iright - 1
   if list[i_] <= pivotValue then do
     list = swap(list, storeIndex, i_)
     storeIndex = storeIndex + 1
     end
   end i_
 list = swap(list, iright, storeIndex) -- Move pivot to its final place
 return storeIndex

-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ method qselectInPlace(list, k_, ileft = -1, iright = -1) public static 

 if ileft  = -1 then ileft  = 1
 if iright = -1 then iright = list[0]

 loop label inplace forever
   pivotIndex = Random().nextInt(iright - ileft + 1) + ileft -- select pivotIndex between left and right
 pivotNewIndex = qpartition(list, ileft, iright, pivotIndex)
 pivotDist = pivotNewIndex - ileft + 1
 select
   when pivotDist = k_ then do
     returnVal = list[pivotNewIndex]
     leave inplace
     end
   when k_ < pivotDist then
     iright = pivotNewIndex - 1
   otherwise do
     k_ = k_ - pivotDist
     ileft = pivotNewIndex + 1
     end
   end    
   end inplace
 return returnVal

-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ method swap(list, i1, i2) private static 

 if i1 \= i2 then do
   t1       = list[i1]
   list[i1] = list[i2]
   list[i2] = t1
   end
 return list

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) private static 

 parse arg samplelist
 if samplelist =  | samplelist = '.' then samplelist = 9 8 7 6 5 0 1 2 3 4
 items = samplelist.words
 say 'Input:'
 say '    'samplelist.space(1, ',').changestr(',', ', ')
 say

 say 'Using in-place version of the algorithm:'
 iv = 
 loop k_ = 1 to items
   iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
   end k_
 say '    'iv.space(1, ',').changestr(',', ', ')
 say

 say 'Find the 4 smallest:'
 iv = 
 loop k_ = 1 to 4
   iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
   end k_
 say '    'iv.space(1, ',').changestr(',', ', ')
 say

 say 'Find the 3 largest:'
 iv = 
 loop k_ = items - 2 to items
   iv = iv qselectInPlace(buildIndexedString(samplelist), k_)
   end k_
 say '    'iv.space(1, ',').changestr(',', ', ')
 say

 return

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method buildIndexedString(samplelist) private static 

 list = 0
 list[0] = samplelist.words()
 loop k_ = 1 to list[0]
   list[k_] = samplelist.word(k_)
   end k_
 return list
 </lang>
Output:
Input:
    9, 8, 7, 6, 5, 0, 1, 2, 3, 4

Using in-place version of the algorithm:
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Find the 4 smallest:
    0, 1, 2, 3

Find the 3 largest:
    7, 8, 9

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

REXX

<lang rexx>/*REXX program sorts a list (which may be numbers) using quick select.*/ parse arg list; if list= then list=9 8 7 6 5 0 1 2 3 4 /*default?*/ 

 do #=1  for words(list);   @.#=word(list,#);   end  /*#*/;         #=#-1
                                      /* [↓]  #=number of items in list*/
     do j=1  for #                    /*show  1 ──► #  place and value.*/
     say '         item'  right(j,length(#))",  value: "      qSel(1,#,j)
     end   /*j*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────QPART subroutine────────────────────*/ qPart: procedure expose @.; parse arg L 1 ?,R,pivotIndex;pVal=@.pivotIndex parse value @.pivotIndex @.R with @.R @.pivotIndex /*swap 2 items*/ 

         do k=L  to R-1               /*process the left side of list. */
         if @.k>pVal  then iterate    /*when item>pivotValue, skip it. */
         parse value  @.? @.k   with    @.k  @.?         /*swap 2 items*/
         ?=?+1                                           /*next item.  */
         end   /*k*/

parse value @.R @.? with @.? @.R /*swap 2 items*/ return ? /*──────────────────────────────────QSEL subroutine─────────────────────*/ qSel: procedure expose @.; parse arg L,R,z; if L==R then return @.L 

 do forever                           /*keep looping until all done.   */
 pivotNewIndex=qPart(L, R, (L+R)%2)   /*partition the list into  ≈  ½. */
 pivotDist=pivotNewIndex-L+1
 if pivotDist==z  then return @.pivotNewIndex
                  else if z<pivotDist  then R=pivotNewIndex-1
                                       else do
                                            z=z-pivotDist
                                            L=pivotNewindex+1
                                            end
 end   /*forever*/</lang>

output   when using the default input: 

         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

Ruby

<lang ruby>def quickselect(a, k) 

 arr = a.dup # we will be modifying it
 loop do
   pivot = arr.delete_at(rand(arr.length))
   left, right = arr.partition { |x| x < pivot }
   if k == left.length
     return pivot
   elsif k < left.length
     arr = left
   else
     k = k - left.length - 1
     arr = right
   end
 end

end

v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] p v.each_index.map { |i| quickselect(v, i) }</lang>

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

Scala

<lang scala>import scala.util.Random

object QuickSelect { 

 def quickSelect[A <% Ordered[A]](seq: Seq[A], n: Int, rand: Random = new Random): A = {
   val pivot = rand.nextInt(seq.length);
   val (left, right) = seq.partition(_ < seq(pivot))
   if (left.length == n) {
     seq(pivot)
   } else if (left.length < n) {
     quickSelect(right, n - left.length, rand)
   } else {
     quickSelect(left, n, rand)
   }
 }
 
 def main(args: Array[String]): Unit = {
   val v = Array(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
   println((0 until v.length).map(quickSelect(v, _)).mkString(", "))
 }

}</lang>

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

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
Retrieved from "https://rosettacode.org/wiki/Quickselect_algorithm?oldid=235262"