Quickselect algorithm: Difference between revisions
m (Fixed typos, changed method name and improved comments.) |
(Not Quicksort but Quickselect.) |
||
Line 4: | Line 4: | ||
To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page. |
To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page. |
||
* Note: Quick''sort'' has a separate [[Sorting algorithms/Quicksort|task]]. |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
Two different implementations - one that returns only one element from the array (Nth smallest element) and |
Two different implementations - one that returns only one element from the array (Nth smallest element) and |
Revision as of 04:23, 6 October 2013
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#
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, Finland 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.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 >
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,
\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