Quickselect algorithm: Difference between revisions
(New draft task and Python solution.) |
(Perl 6) |
||
Line 3: | Line 3: | ||
: [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] |
: [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. |
To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page. |
||
=={{header|Perl 6}}== |
|||
{{trans|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, $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> |
|||
{{out}} |
|||
<pre>0 1 2 3 4 5 6 7 8 9</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 15:16, 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]