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.
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 // // Mikko Puonti 2013 // // ----------------------------------------------------------------------------------------------
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.TakeNthSmallest( 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 smmallest 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 TakeNthSmallest<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 ];
}
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();
// Selecting initial pivot
var startIndex = 0;
var endIndex = input.Length - 1;
var r = new Random();
// Maybe we are lucky and array is sorted initially?
var pivotIndex = n;
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...
// Select new pivot index between end and start indexes
pivotIndex = r.Next( endIndex - startIndex + 1 ) + startIndex;
}
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 smmallest and sort them. 0, 1, 2, 3 < Press any key >
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
<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 where @vector,
\k where (1 .. @vector),
\l where (0 .. @vector) = 0,
\r where (l .. @vector) = @vector.end ) {
my $k = k; my $left = l; my $right = 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 >= 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
<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