Quickselect algorithm: Difference between revisions

{{trans|Python}}

 

V pivotValue = vector[pivotIndex]

swap(&vector[pivotIndex], &vector[right])

 

V v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

 

{{out}}

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

</pre>

 

=={{header|ALGOL 68}}==

# returns the kth lowest element of list using the quick select algorithm #

PRIO QSELECT = 1;

print( ( whole( i, -2 ), ": ", whole( i QSELECT test, -3 ), newline ) )

OD

{{out}}

<pre>

 

===Procedural===

script o

property lst : theList's items -- Shallow copy.

set end of selected to quickselect(theVector, 1, vectorLength, i)

end repeat

 

{{out}}

 

===Functional===

 

-- quickSelect :: Ord a => [a] -> Int -> a

end tell

{ys, zs}

{{Out}}

<pre>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}</pre>

 

=={{header|Arturo}}==

 

arr: new a

while ø [

 

print map 0..(size v)-1 'i ->

 

{{out}}

 

<pre>0 1 2 3 4 5 6 7 8 9</pre>

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}} (AutoHotkey1.1+)

A direct implementation of the Wikipedia pseudo-code.

Loop, 10

Out .= Select(MyList, 1, MyList.MaxIndex(), A_Index) (A_Index = MyList.MaxIndex() ? "" : ", ")

, List[i1] := List[i2]

, List[i2] := t

'''Output:'''

<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9 </pre>

 

=={{header|C}}==

#include <string.h>

 

 

return 0;

{{out}}

<pre>

second implementation that returns IEnumnerable that enumerates through element until Nth smallest element.

//

// Program.cs - QuickSelect

#endregion

}

{{out}}

<pre>Loop quick select 10 times.

 

It is already provided in the standard library as <code>std::nth_element()</code>. 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.

#include <iostream>

 

 

return 0;

 

{{out}}

 

A more explicit implementation:

#include <algorithm>

#include <functional>

 

return 0;

 

{{out}}

<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>

 

=={{header|COBOL}}==

The following is in the Managed COBOL dialect:

{{works with|Visual COBOL}}

METHOD-ID Partition STATIC USING T.

DISPLAY SPACE

END METHOD.

 

=={{header|Common Lisp}}==

{{trans|Haskell}}

(defun quickselect (n _list)

(let* ((ys (remove-if (lambda (x) (< (car _list) x)) (cdr _list)))

(defparameter a '(9 8 7 6 5 0 1 2 3 4))

(format t "~a~&" (mapcar (lambda (x) (quickselect x a)) (loop for i from 0 below (length a) collect i)))

{{out}}

<pre>

=={{header|Crystal}}==

{{trans|Ruby}}

arr = a.dup # we will be modifying it

loop do

v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

p v.each_index.map { |i| quickselect(v, i) }.to_a

{{out}}

<pre>

===Standard Version===

This could use a different algorithm:

import std.stdio, std.algorithm;

 

write(a[i], " ");

}

{{out}}

<pre>0 1 2 3 4 5 6 7 8 9 </pre>

===Array Version===

{{trans|Java}}

 

T quickSelect(T)(T[] arr, size_t n)

auto a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];

a.length.iota.map!(i => a.quickSelect(i)).writeln;

{{out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Quickselect_algorithm;

 

end;

Readln;

 

=={{header|Elixir}}==

{{trans|Erlang}}

def select(k, [x|xs]) do

{ys, zs} = Enum.partition(xs, fn e -> e < x end)

end

 

 

{{out}}

{{trans|Haskell}}

 

-module(quickselect).

 

X

end.

 

Output:

=={{header|F Sharp|F#}}==

{{trans|Haskell}}

let rec quickselect k list =

match list with

printfn "%A" [for i in 0..(List.length v - 1) -> quickselect i v]

0

{{out}}

<pre>[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]</pre>

=={{header|Factor}}==

{{trans|Haskell}}

IN: rosetta-code.quickselect

 

[ [ quickselect , ] curry each ] { } make . ;

 

{{out}}

<pre>

Conveniently, a function was already to hand for floating-point numbers and changing the type was trivial - because the array and its associates were declared in the same statement to facilitate exactly that. The style is F77 (except for the A(1:N) usage in the DATA statement, and the END FUNCTION usage) and it did not seem worthwhile activating the MODULE protocol of F90 just to save the tedium of having to declare INTEGER FINDELEMENT in the calling routine - doing so would require four additional lines... On the other hand, a MODULE would enable the convenient development of a collection of near-clones, one for each type of array (INTEGER, REAL*4, REAL*8) which could then be collected via an INTERFACE statement into forming an apparently generic function so that one needn't have to remember FINDELEMENTI2, FINDELEMENTI4, FINDELEMENTF4, FINDELEMENTF8, and so on. With multiple parameters of various types, the combinations soon become tiresomely numerous.

 

Chase an order statistic: FindElement(N/2,A,N) leads to the median, with some odd/even caution.

Careful! The array is shuffled: for i < K, A(i) <= A(K); for i > K, A(i) >= A(K).

END DO !On to the next trial.

 

 

To demonstrate that the array, if unsorted, will likely have elements re-positioned, the array's state after each call is shown.<pre>Selection of the i'th element in order from an array.

=={{header|FreeBASIC}}==

Una implementación directa del pseudocódigo de Wikipedia.

Dim Shared As Long array(9), pivote

 

Next i

Sleep

{{out}}

<pre>

 

=={{header|Go}}==

 

import "fmt"

fmt.Println(quickselect(v, i))

}

{{out}}

<pre>

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

 

 

import (

fmt.Println(v[quickselect(sort.IntSlice(v), i)])

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

quickselect

print

((fmap . quickselect) <*> zipWith const [0 ..] $

{{out}}

<pre>[0,1,2,3,4,5,6,7,8,9]</pre>

 

The following works in both languages.

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

end

A[max] :=: A[sI]

return sI

 

Sample run:

With that out of the way, here's a pedantic (and laughably inefficient) implementation of quickselect:

 

if. 0=#y do. _ return. end.

n=.?#y

end.

end.

 

"Proof" that it works:

 

 

And, the required task example:

 

 

(Insert here: puns involving greater transparency, the emperor's new clothes, burlesque and maybe the dance of the seven veils.)

 

=={{header|Java}}==

 

public class QuickSelect {

}

 

 

{{out}}

=={{header|Javascript}}==

===ES5===

function swap(items, firstIndex, secondIndex) {

var temp = items[firstIndex];

// return quickselectIterative(array, k);

}

 

'''Example''':

var array = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4],

ks = Array.apply(null, {length: 10}).map(Number.call, Number);

{{out}}

 

===ES6===

{{Trans|Haskell}}

'use strict';

 

 

return map(i => quickSelect(i, v), enumFromTo(0, length(v) - 1));

{{Out}}

 

=={{header|jq}}==

{{works with|jq|1.4}}

# or nothing if k is too small or too large.

# The smallest corresponds to k==1.

end;

 

 

'''Example''':

Notice that values of k that are too large or too small generate nothing.

| [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] | quickselect($k)

{{out}}

k=1 => 0

k=2 => 1

k=9 => 8

k=10 => 9

 

=={{header|Julia}}==

 

 

{{out}}

<pre>v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

 

=={{header|Kotlin}}==

 

const val MAX = Int.MAX_VALUE

}

println()

 

{{out}}

 

=={{header|Lua}}==

local pivotValue = list[pivotIndex]

list[pivotIndex], list[right] = list[right], list[pivotIndex]

math.randomseed(os.time())

local vec = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}

{{out}}

<pre>1 0

 

=={{header|Maple}}==

local val,safe,i:

val := arr[pivot]:

map(x->printf("%d ", x), demo):

print(quickselect(demo,7)):

{{Out|Example}}

<pre>5 4 2 1 3 6 8 11 11 11 8 11 9 11 16 20 20 18 17 16

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0},

While[True,

];

ds = CreateDataStructure["DynamicArray", {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}];

{{out}}

<pre>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}</pre>

 

=={{header|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> */

end k_

return list

{{out}}

<pre>

 

=={{header|Nim}}==

var r = if inr >= 0: inr else: a.high

var st = 0

for i in 0..9:

var y = x

Output:

<pre>0: 0

 

=={{header|OCaml}}==

[] -> failwith "empty"

| x :: xs -> let ys, zs = List.partition ((>) x) xs in

quickselect (k-l-1) zs

else

Usage:

<pre>

 

=={{header|PARI/GP}}==

my(pivotValue=list[pivotIndex],storeIndex=left,t);

t=list[pivotIndex];

quickselect(list, pivotIndex + 1, right, n)

)

 

=={{header|Perl}}==

print join ' ', map { qselect(\@list, $_) } 1 .. 10 and print "\n";

 

}

else { $pivot }

 

{{out}}

 

=={{header|Phix}}==

<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">}</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

0 1 2 3 4 5 6 7 8 9

</pre>

 

=={{header|PicoLisp}}==

(de swapL (Lst X Y)

(let L (nth Lst Y)

(mapcar

'((N) (quick Lst N))

{{out}}

<pre>(0 1 2 3 4 5 6 7 8 9)</pre>

 

=={{header|PL/I}}==

quick: procedure options (main); /* 4 April 2014 */

 

end;

 

Output:

<pre>

 

=={{header|PowerShell}}==

function partition($list, $left, $right, $pivotIndex) {

$pivotValue = $list[$pivotIndex]

$arr = @(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)

"$(quickselect $arr)"

<b>Output:</b>

<pre>

=={{header|PureBasic}}==

A direct implementation of the Wikipedia pseudo-code.

Procedure QuickPartition (Array L(1), left, right, pivotIndex)

pivotValue = L(pivotIndex)

For i=0 To 9

Debug QuickSelect(L(),0,9,i)

{{out}}

<pre>0 1 2 3 4 5 6 7 8 9</pre>

===Procedural===

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.

 

def partition(vector, left, right, pivotIndex):

if __name__ == '__main__':

v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

 

{{out}}

{{Trans|Haskell}}

{{Works with|Python|3}}

 

from functools import reduce

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

 

=={{header|Racket}}==

(define pivot (list-ref A (random (length A))))

(define A1 (filter (curry > pivot) A))

(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)))) ", "))

{{out}}

<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>

{{trans|Python}}

{{works with|rakudo|2015-10-20}}

say map { select(@v, $_) }, 1 .. 10;

}

}

{{out}}

<pre>0 1 2 3 4 5 6 7 8 9</pre>

=={{header|REXX}}==

===uses in-line swap===

parse arg list; if list='' then list= 9 8 7 6 5 0 1 2 3 4 /*Not given? Use default.*/

say right('list: ', 22) list

L= new+1 /*increase the left half *f the array.*/

end

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

===uses swap subroutine===

parse arg list; if list='' then list= 9 8 7 6 5 0 1 2 3 4 /*Not given? Use default.*/

say right('list: ', 22) list

end /*forever*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; is the identical to the 1^st REXX version.}} <br><br>

 

=={{header|Ring}}==

aList = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

see partition(aList, 9, 4, 2) + nl

next

return storeIndex

 

=={{header|Ruby}}==

arr = a.dup # we will be modifying it

loop do

 

v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

 

{{out}}

 

=={{header|Rust}}==

 

fn partition<T: PartialOrd>(a: &mut [T], left: usize, right: usize, pivot: usize) -> usize {

println!("n = {}, nth element = {}", n + 1, b[n]);

}

 

{{out}}

 

=={{header|Scala}}==

 

object QuickSelect {

println((0 until v.length).map(quickSelect(v, _)).mkString(", "))

}

 

{{out}}

<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>

 

=={{header|Sidef}}==

 

}

}

 

{{out}}

<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

 

=={{header|Standard ML}}==

| quickselect (k, cmp, x :: xs) = let

val (ys, zs) = List.partition (fn y => cmp (y, x) = LESS) xs

else

x

Usage:

<pre>

 

=={{header|Swift}}==

var r = indices(elements)

while true {

if i < 9 { print(", ") }

}

 

{{out}}

=={{header|Tcl}}==

{{trans|Python}}

proc swap {list i j} {

upvar 1 $list l

}

}

Demonstrating:

foreach i {1 2 3 4 5 6 7 8 9 10} {

puts "$i => [quickselect $v $i]"

{{out}}

<pre>

 

=={{header|VBA}}==

Private Function quick_select(ByRef s As Variant, k As Integer) As Integer

Dim left As Integer, right As Integer, pos As Integer

Next i

End Sub

<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>

 

{{libheader|Wren-sort}}

The Find.quick method in the above module implements the quickselect algorithm.

 

var a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

if (k < 9) System.write(", ")

}

 

{{out}}

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

</pre>

 

=={{header|zkl}}==

{{trans|Wikipedia}}

This is the in place version rather than the much more concise copy-partition functional method. A copy of the input list is made to cover the case it is immutable (or the input shouldn't be changed)

fcn(list,left,right,nth){

if (left==right) return(list[left]);

return(self.fcn(list,pivotIndex+1,right,nth));

}(list.copy(),0,list.len()-1,nth);

{{out}}

<pre>