Quickselect algorithm: Difference between revisions
(Perl 6) |
(→Tcl: Added implementation) |
||
Line 101: | Line 101: | ||
{{out}} |
{{out}} |
||
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre> |
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre> |
||
=={{header|Tcl}}== |
|||
{{trans|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> |
|||
{{out}} |
|||
<pre> |
|||
1 => 0 |
|||
2 => 1 |
|||
3 => 2 |
|||
4 => 3 |
|||
5 => 4 |
|||
6 => 5 |
|||
7 => 6 |
|||
8 => 7 |
|||
9 => 8 |
|||
10 => 9 |
|||
</pre> |
Revision as of 18:24, 28 September 2013
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.
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, $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
<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