Quickselect algorithm: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(10 intermediate revisions by 6 users not shown) | |||
Line 12:
{{trans|Python}}
<
V pivotValue = vector[pivotIndex]
swap(&vector[pivotIndex], &vector[right])
Line 51:
V v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print((0.<10).map(i -> select(&:v, i)))</
{{out}}
<pre>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program quickSelection64.s */
/* look pseudo code in wikipedia quickselect */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResultIndex: .asciz "index : "
szMessResultValue: .asciz " value : "
szCarriageReturn: .asciz "\n"
szMessStart: .asciz "Program 64 bits start.\n"
.align 4
TableNumber: .quad 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrszMessStart
bl affichageMess
mov x6,#0
1:
ldr x0,qAdrTableNumber // address number table
mov x1,#0 // index first item
mov x2,#NBELEMENTS -1 // index last item
mov x3,x6 // search index
bl select // call selection
ldr x1,qAdrsZoneConv
bl conversion10 // convert result to decimal
mov x0,x6
ldr x1,qAdrsZoneConv1
bl conversion10 // convert index to decimal
mov x0,#5 // and display result
ldr x1,qAdrszMessResultIndex
ldr x2,qAdrsZoneConv1
ldr x3,qAdrszMessResultValue
ldr x4,qAdrsZoneConv
ldr x5,qAdrszCarriageReturn
bl displayStrings
add x6,x6,#1
cmp x6,#NBELEMENTS
blt 1b
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrTableNumber: .quad TableNumber
qAdrsZoneConv: .quad sZoneConv
qAdrsZoneConv1: .quad sZoneConv1
qAdrszMessResultIndex: .quad szMessResultIndex
qAdrszMessResultValue: .quad szMessResultValue
qAdrszMessStart: .quad szMessStart
/***************************************************/
/* Appel récursif selection */
/***************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item */
/* x2 contains index of last item */
/* x3 contains search index */
select:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
mov x6,x3 // save search index
cmp x1,x2 // first = last ?
bne 1f
ldr x0,[x0,x1,lsl #3] // return value of first index
b 100f // yes -> end
1:
add x3,x1,x2
lsr x3,x3,#1 // compute median pivot
mov x4,x0 // save x0
mov x5,x2 // save x2
bl partition // cutting.quado 2 parts
cmp x6,x0 // pivot is ok ?
bne 2f
ldr x0,[x4,x0,lsl #3] // yes -> return value
b 100f
2:
bgt 3f
sub x2,x0,#1 // index partition - 1
mov x0,x4 // array address
mov x3,x6 // search index
bl select // select lower part
b 100f
3:
add x1,x0,#1 // index begin = index partition + 1
mov x0,x4 // array address
mov x2,x5 // last item
mov x3,x6 // search index
bl select // select higter part
100: // end function
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* Partition table elements */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains index of first item */
/* x2 contains index of last item */
/* x3 contains index of pivot */
partition:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
ldr x4,[x0,x3,lsl #3] // load value of pivot
ldr x5,[x0,x2,lsl #3] // load value last index
str x5,[x0,x3,lsl #3] // swap value of pivot
str x4,[x0,x2,lsl #3] // and value last index
mov x3,x1 // init with first index
1: // begin loop
ldr x6,[x0,x3,lsl #3] // load value
cmp x6,x4 // compare loop value and pivot value
bge 2f
ldr x5,[x0,x1,lsl #3] // if < swap value table
str x6,[x0,x1,lsl #3]
str x5,[x0,x3,lsl #3]
add x1,x1,#1 // and increment index 1
2:
add x3,x3,#1 // increment index 2
cmp x3,x2 // end ?
blt 1b // no loop
ldr x5,[x0,x1,lsl #3] // swap value
str x4,[x0,x1,lsl #3]
str x5,[x0,x2,lsl #3]
mov x0,x1 // return index partition
100:
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/***************************************************/
/* display multi strings */
/* new version 24/05/2023 */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* x4 address string4 */
/* x5 address string5 */
/* x6 address string5 */
/* x7 address string6 */
displayStrings: // INFO: displayStrings
stp x8,lr,[sp,-16]! // save registers
stp x2,fp,[sp,-16]! // save registers
add fp,sp,#32 // save paraméters address (4 registers saved * 8 bytes)
mov x8,x0 // save strings number
cmp x8,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x8,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x8,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x8,#3
ble 100f
mov x0,x4
bl affichageMess
cmp x8,#4
ble 100f
mov x0,x5
bl affichageMess
cmp x8,#5
ble 100f
mov x0,x6
bl affichageMess
cmp x8,#6
ble 100f
mov x0,x7
bl affichageMess
100:
ldp x2,fp,[sp],16 // restaur registers
ldp x8,lr,[sp],16 // restaur registers
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 64 bits start.
index : 0 value : 0
index : 1 value : 1
index : 2 value : 2
index : 3 value : 3
index : 4 value : 4
index : 5 value : 5
index : 6 value : 6
index : 7 value : 7
index : 8 value : 8
index : 9 value : 9
</pre>
=={{header|Action!}}==
<
BYTE tmp
Line 109 ⟶ 340:
PrintB(res) Put(32)
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Quickselect_algorithm.png Screenshot from Atari 8-bit computer]
Line 123 ⟶ 354:
I implement a generic partition and a generic quickselect and apply them to an array of integers. The order predicate is passed as a parameter, and I demonstrate both '''<''' and '''>''' as the predicate.
<
with Ada.Numerics.Float_Random;
Line 379 ⟶ 610:
end quickselect_task;
----------------------------------------------------------------------</
{{out}}
Line 387 ⟶ 618:
=={{header|ALGOL 68}}==
<
# returns the kth lowest element of list using the quick select algorithm #
PRIO QSELECT = 1;
Line 443 ⟶ 674:
print( ( whole( i, -2 ), ": ", whole( i QSELECT test, -3 ), newline ) )
OD
END</
{{out}}
<pre>
Line 461 ⟶ 692:
===Procedural===
<
script o
property lst : theList's items -- Shallow copy.
Line 582 ⟶ 813:
set end of selected to quickselect(theVector, 1, vectorLength, i)
end repeat
return selected</
{{out}}
<
===Functional===
<
-- quickSelect :: Ord a => [a] -> Int -> a
Line 696 ⟶ 927:
end tell
{ys, zs}
end partition</
{{Out}}
<pre>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program quickSelection.s */
/* look pseudo code in wikipedia quickselect */
/************************************/
/* Constantes */
/************************************/
/* for constantes see task include a file in arm assembly */
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResultIndex: .asciz "index : "
szMessResultValue: .asciz " value : "
szCarriageReturn: .asciz "\n"
.align 4
TableNumber: .int 9, 8, 7, 6, 5, 0, 1, 2, 3, 4
.equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
sZoneConv1: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
mov r5,#0
1:
ldr r0,iAdrTableNumber @ address number table
mov r1,#0 @ index first item
mov r2,#NBELEMENTS -1 @ index last item
mov r3,r5 @ search index
bl select @ call selection
ldr r1,iAdrsZoneConv
bl conversion10 @ convert result to decimal
mov r0,r5
ldr r1,iAdrsZoneConv1
bl conversion10 @ convert index to decimal
mov r0,#5 @ and display result
ldr r1,iAdrszMessResultIndex
ldr r2,iAdrsZoneConv1
ldr r3,iAdrszMessResultValue
ldr r4,iAdrsZoneConv
push {r4}
ldr r4,iAdrszCarriageReturn
push {r4}
bl displayStrings
add sp,sp,#8 @ stack alignement (2 push)
add r5,r5,#1
cmp r5,#NBELEMENTS
blt 1b
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrszCarriageReturn: .int szCarriageReturn
iAdrTableNumber: .int TableNumber
iAdrsZoneConv: .int sZoneConv
iAdrsZoneConv1: .int sZoneConv1
iAdrszMessResultIndex: .int szMessResultIndex
iAdrszMessResultValue: .int szMessResultValue
/***************************************************/
/* Appel récursif selection */
/***************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item */
/* r2 contains index of last item */
/* r3 contains search index */
select:
push {r1-r6,lr} @ save registers
mov r6,r3 @ save search index
cmp r1,r2 @ first = last ?
ldreq r0,[r0,r1,lsl #2] @ return value of first index
beq 100f @ yes -> end
add r3,r1,r2
lsr r3,r3,#1 @ compute median pivot
mov r4,r0 @ save r0
mov r5,r2 @ save r2
bl partition @ cutting into 2 parts
cmp r6,r0 @ pivot is ok ?
ldreq r0,[r4,r0,lsl #2] @ return value
beq 100f
bgt 1f
sub r2,r0,#1 @ index partition - 1
mov r0,r4 @ array address
mov r3,r6 @ search index
bl select @ select lower part
b 100f
1:
add r1,r0,#1 @ index begin = index partition + 1
mov r0,r4 @ array address
mov r2,r5 @ last item
mov r3,r6 @ search index
bl select @ select higter part
100: @ end function
pop {r1-r6,pc} @ restaur register
/******************************************************************/
/* Partition table elements */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains index of first item */
/* r2 contains index of last item */
/* r3 contains index of pivot */
partition:
push {r1-r6,lr} @ save registers
ldr r4,[r0,r3,lsl #2] @ load value of pivot
ldr r5,[r0,r2,lsl #2] @ load value last index
str r5,[r0,r3,lsl #2] @ swap value of pivot
str r4,[r0,r2,lsl #2] @ and value last index
mov r3,r1 @ init with first index
1: @ begin loop
ldr r6,[r0,r3,lsl #2] @ load value
cmp r6,r4 @ compare loop value and pivot value
ldrlt r5,[r0,r1,lsl #2] @ if < swap value table
strlt r6,[r0,r1,lsl #2]
strlt r5,[r0,r3,lsl #2]
addlt r1,#1 @ and increment index 1
add r3,#1 @ increment index 2
cmp r3,r2 @ end ?
blt 1b @ no loop
ldr r5,[r0,r1,lsl #2] @ swap value
str r4,[r0,r1,lsl #2]
str r5,[r0,r2,lsl #2]
mov r0,r1 @ return index partition
100:
pop {r1-r6,pc}
/***************************************************/
/* display multi strings */
/***************************************************/
/* r0 contains number strings address */
/* r1 address string1 */
/* r2 address string2 */
/* r3 address string3 */
/* other address on the stack */
/* thinck to add number other address * 4 to add to the stack */
displayStrings: @ INFO: displayStrings
push {r1-r4,fp,lr} @ save des registres
add fp,sp,#24 @ save paraméters address (6 registers saved * 4 bytes)
mov r4,r0 @ save strings number
cmp r4,#0 @ 0 string -> end
ble 100f
mov r0,r1 @ string 1
bl affichageMess
cmp r4,#1 @ number > 1
ble 100f
mov r0,r2
bl affichageMess
cmp r4,#2
ble 100f
mov r0,r3
bl affichageMess
cmp r4,#3
ble 100f
mov r3,#3
sub r2,r4,#4
1: @ loop extract address string on stack
ldr r0,[fp,r2,lsl #2]
bl affichageMess
subs r2,#1
bge 1b
100:
pop {r1-r4,fp,pc}
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"
</syntaxhighlight>
{{Out}}
<pre>
index : 0 value : 0
index : 1 value : 1
index : 2 value : 2
index : 3 value : 3
index : 4 value : 4
index : 5 value : 5
index : 6 value : 6
index : 7 value : 7
index : 8 value : 8
index : 9 value : 9
</pre>
=={{header|Arturo}}==
<
arr: new a
while ø [
Line 724 ⟶ 1,152:
print map 0..(size v)-1 'i ->
quickselect v i</
{{out}}
Line 734 ⟶ 1,162:
=== Quickselect working on linear lists ===
There is also a stable quicksort here. See it demonstrated at [[Quicksort#A_stable_quicksort_working_on_linear_lists|the quicksort task]].
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
(*
Line 1,370 ⟶ 1,800:
end
(*------------------------------------------------------------------*)</
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC quickselect_task_for_list_vt.dats && ./a.out quickselect
With < as order predicate: 0 1 2 3 4 5 6 7 8 9
With > as order predicate: 9 8 7 6 5 4 3 2 1 0</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() ? "" : ", ")
Line 1,414 ⟶ 1,848:
, 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>
Line 1,453 ⟶ 1,887:
return 0;
}</
{{out}}
<pre>
Line 1,472 ⟶ 1,906:
second implementation that returns IEnumnerable that enumerates through element until Nth smallest element.
<
//
// Program.cs - QuickSelect
Line 1,644 ⟶ 2,078:
#endregion
}
}</
{{out}}
<pre>Loop quick select 10 times.
Line 1,659 ⟶ 2,093:
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>
Line 1,672 ⟶ 2,106:
return 0;
}</
{{out}}
Line 1,680 ⟶ 2,114:
A more explicit implementation:
<
#include <algorithm>
#include <functional>
Line 1,716 ⟶ 2,150:
return 0;
}</
{{out}}
Line 1,722 ⟶ 2,156:
=={{header|CLU}}==
<
where T has lt: proctype (T,T) returns (bool)
aT = array[T]
Line 1,777 ⟶ 2,211:
stream$putl(po, int$unparse(k) || ": " || int$unparse(item))
end
end start_up</
{{out}}
<pre>1: 0
Line 1,793 ⟶ 2,227:
The following is in the Managed COBOL dialect:
{{works with|Visual COBOL}}
<
METHOD-ID Partition STATIC USING T.
Line 1,887 ⟶ 2,321:
DISPLAY SPACE
END METHOD.
END CLASS.</
=={{header|Common Lisp}}==
{{trans|Haskell}}
<
(defun quickselect (n _list)
(let* ((ys (remove-if (lambda (x) (< (car _list) x)) (cdr _list)))
Line 1,905 ⟶ 2,339:
(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)))
</syntaxhighlight>
{{out}}
<pre>
Line 1,913 ⟶ 2,347:
=={{header|Crystal}}==
{{trans|Ruby}}
<
arr = a.dup # we will be modifying it
loop do
Line 1,931 ⟶ 2,365:
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
p v.each_index.map { |i| quickselect(v, i) }.to_a
</syntaxhighlight>
{{out}}
<pre>
Line 1,940 ⟶ 2,374:
===Standard Version===
This could use a different algorithm:
<
import std.stdio, std.algorithm;
Line 1,948 ⟶ 2,382:
write(a[i], " ");
}
}</
{{out}}
<pre>0 1 2 3 4 5 6 7 8 9 </pre>
Line 1,954 ⟶ 2,388:
===Array Version===
{{trans|Java}}
<
T quickSelect(T)(T[] arr, size_t n)
Line 2,001 ⟶ 2,435:
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>
Line 2,007 ⟶ 2,441:
{{libheader| System.SysUtils}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Quickselect_algorithm;
Line 2,067 ⟶ 2,501:
end;
Readln;
end.</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc qselect k . list[] res .
#
subr
swap list[i] list[mid]
.
.
swap list[left] list[mid]
.
left = 1
right = len
while left < right
right = mid - 1
left = right
.
res = list[k]
.
d[] = [ 9 8 7 6 5 0 1 2 3 4 ]
for i
print r
.
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
def select(k, [x|xs]) do
{ys, zs} = Enum.partition(xs, fn e -> e < x end)
Line 2,121 ⟶ 2,558:
end
Quick.test</
{{out}}
Line 2,131 ⟶ 2,568:
{{trans|Haskell}}
<
-module(quickselect).
Line 2,156 ⟶ 2,593:
X
end.
</syntaxhighlight>
Output:
Line 2,165 ⟶ 2,602:
=={{header|F Sharp|F#}}==
{{trans|Haskell}}
<
let rec quickselect k list =
match list with
Line 2,183 ⟶ 2,620:
printfn "%A" [for i in 0..(List.length v - 1) -> quickselect i v]
0
</syntaxhighlight>
{{out}}
<pre>[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]</pre>
Line 2,189 ⟶ 2,626:
=={{header|Factor}}==
{{trans|Haskell}}
<
IN: rosetta-code.quickselect
Line 2,206 ⟶ 2,643:
[ [ quickselect , ] curry each ] { } make . ;
MAIN: quickselect-demo</
{{out}}
<pre>
Line 2,215 ⟶ 2,652:
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.
Those of a delicate disposition may wish to avert their eyes from the three-way IF-statement... <
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).
Line 2,265 ⟶ 2,702:
END DO !On to the next trial.
END !That was easy.</
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.
Line 2,288 ⟶ 2,725:
=={{header|FreeBASIC}}==
Una implementación directa del pseudocódigo de Wikipedia.
<
Dim Shared As Long array(9), pivote
Line 2,334 ⟶ 2,771:
Next i
Sleep
</syntaxhighlight>
{{out}}
<pre>
Line 2,343 ⟶ 2,780:
=={{header|Go}}==
<
import "fmt"
Line 2,383 ⟶ 2,820:
fmt.Println(quickselect(v, i))
}
}</
{{out}}
<pre>
Line 2,400 ⟶ 2,837:
A more generic version that works for any container that conforms to <code>sort.Interface</code>:
<
import (
Line 2,454 ⟶ 2,891:
fmt.Println(v[quickselect(sort.IntSlice(v), i)])
}
}</
{{out}}
<pre>
Line 2,470 ⟶ 2,907:
=={{header|Haskell}}==
<
quickselect
Line 2,487 ⟶ 2,924:
print
((fmap . quickselect) <*> zipWith const [0 ..] $
[9, 8, 7, 6, 5, 0, 1, 2, 3, 4])</
{{out}}
<pre>[0,1,2,3,4,5,6,7,8,9]</pre>
Line 2,494 ⟶ 2,931:
The following works in both languages.
<
every writes(" ",select(1 to *A, A, 1, *A)|"\n")
end
Line 2,514 ⟶ 2,951:
A[max] :=: A[sI]
return sI
end</
Sample run:
Line 2,535 ⟶ 2,972:
With that out of the way, here's a pedantic (and laughably inefficient) implementation of quickselect:
<
if. 0=#y do. _ return. end.
n=.?#y
Line 2,548 ⟶ 2,985:
end.
end.
)</
"Proof" that it works:
<
8</
And, the required task example:
<
0 1 2 3 4 5 6 7 8 9</
(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 {
Line 2,615 ⟶ 3,052:
}
}</
{{out}}
Line 2,622 ⟶ 3,059:
=={{header|Javascript}}==
===ES5===
<
function swap(items, firstIndex, secondIndex) {
var temp = items[firstIndex];
Line 2,692 ⟶ 3,129:
// return quickselectIterative(array, k);
}
}</
'''Example''':
<syntaxhighlight lang="javascript">
var array = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4],
ks = Array.apply(null, {length: 10}).map(Number.call, Number);
ks.map(k => { KthElement.find(array, k) });</
{{out}}
<
===ES6===
{{Trans|Haskell}}
<
'use strict';
Line 2,755 ⟶ 3,192:
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.
Line 2,790 ⟶ 3,227:
end;
if length < k or k <= 0 then empty else [k-1, .] | qs 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)
| "k=\($k) => \(.)"</
{{out}}
<
k=1 => 0
k=2 => 1
Line 2,809 ⟶ 3,246:
k=9 => 8
k=10 => 9
$</
=={{header|Julia}}==
Using builtin function <code>partialsort</code>:
<
@show v partialsort(v, 1:10)
</syntaxhighlight>
{{out}}
Line 2,823 ⟶ 3,260:
=={{header|Kotlin}}==
<
const val MAX = Int.MAX_VALUE
Line 2,867 ⟶ 3,304:
}
println()
}</
{{out}}
Line 2,875 ⟶ 3,312:
=={{header|Lua}}==
<
local pivotValue = list[pivotIndex]
list[pivotIndex], list[right] = list[right], list[pivotIndex]
Line 2,907 ⟶ 3,344:
math.randomseed(os.time())
local vec = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}
for i = 1, 10 do print(i, quickSelect(vec, 1, #vec, i) .. " ") end</
{{out}}
<pre>1 0
Line 2,921 ⟶ 3,358:
=={{header|Maple}}==
<
local val,safe,i:
val := arr[pivot]:
Line 2,956 ⟶ 3,393:
map(x->printf("%d ", x), demo):
print(quickselect(demo,7)):
print(quickselect(demo,14)):</
{{Out|Example}}
<pre>5 4 2 1 3 6 8 11 11 11 8 11 9 11 16 20 20 18 17 16
Line 2,963 ⟶ 3,400:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0},
While[True,
Line 2,992 ⟶ 3,429:
];
ds = CreateDataStructure["DynamicArray", {9, 8, 7, 6, 5, 0, 1, 2, 3, 4}];
Quickselect[ds, #] & /@ Range[10]</
{{out}}
<pre>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}</pre>
Line 3,000 ⟶ 3,437:
<
:- module quickselect_task.
Line 3,209 ⟶ 3,646:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 3,217 ⟶ 3,654:
=={{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> */
Line 3,314 ⟶ 3,751:
end k_
return list
</
{{out}}
<pre>
Line 3,331 ⟶ 3,768:
=={{header|Nim}}==
<
var r = if inr >= 0: inr else: a.high
var st = 0
Line 3,349 ⟶ 3,786:
for i in 0..9:
var y = x
echo i, ": ", qselect(y, i)</
Output:
<pre>0: 0
Line 3,363 ⟶ 3,800:
=={{header|OCaml}}==
<
[] -> failwith "empty"
| x :: xs -> let ys, zs = List.partition ((>) x) xs in
Line 3,372 ⟶ 3,809:
quickselect (k-l-1) zs
else
x</
Usage:
<pre>
Line 3,382 ⟶ 3,819:
=={{header|PARI/GP}}==
<
my(pivotValue=list[pivotIndex],storeIndex=left,t);
t=list[pivotIndex];
Line 3,409 ⟶ 3,846:
quickselect(list, pivotIndex + 1, right, n)
)
};</
=={{header|Perl}}==
<
print join ' ', map { qselect(\@list, $_) } 1 .. 10 and print "\n";
Line 3,430 ⟶ 3,867:
}
else { $pivot }
}</
{{out}}
Line 3,436 ⟶ 3,873:
=={{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>
Line 3,467 ⟶ 3,904:
<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>
Line 3,475 ⟶ 3,912:
=={{header|Picat}}==
From the Wikipedia algorithm.
<
L = [9,8,7,6,5,0,1,2,3,4],
Len = L.len,
Line 3,511 ⟶ 3,948:
T = L[I],
L[I] := L[J],
L[J] := T.</
{{out}}
Line 3,517 ⟶ 3,954:
=={{header|PicoLisp}}==
<
(de swapL (Lst X Y)
(let L (nth Lst Y)
Line 3,546 ⟶ 3,983:
(mapcar
'((N) (quick Lst N))
(range 0 9) ) ) )</
{{out}}
<pre>(0 1 2 3 4 5 6 7 8 9)</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
quick: procedure options (main); /* 4 April 2014 */
Line 3,610 ⟶ 4,047:
end;
end quick;</
Output:
<pre>
Line 3,626 ⟶ 4,063:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function partition($list, $left, $right, $pivotIndex) {
$pivotValue = $list[$pivotIndex]
Line 3,658 ⟶ 4,095:
$arr = @(9, 8, 7, 6, 5, 0, 1, 2, 3, 4)
"$(quickselect $arr)"
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 3,666 ⟶ 4,103:
=={{header|PureBasic}}==
A direct implementation of the Wikipedia pseudo-code.
<syntaxhighlight lang="purebasic">
Procedure QuickPartition (Array L(1), left, right, pivotIndex)
pivotValue = L(pivotIndex)
Line 3,703 ⟶ 4,140:
For i=0 To 9
Debug QuickSelect(L(),0,9,i)
Next i</
{{out}}
<pre>0 1 2 3 4 5 6 7 8 9</pre>
Line 3,710 ⟶ 4,147:
===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):
Line 3,754 ⟶ 4,191:
if __name__ == '__main__':
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
print([select(v, i) for i in range(10)])</
{{out}}
Line 3,762 ⟶ 4,199:
{{Trans|Haskell}}
{{Works with|Python|3}}
<
from functools import reduce
Line 3,819 ⟶ 4,256:
# MAIN ---
if __name__ == '__main__':
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))
Line 3,835 ⟶ 4,272:
(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)))) ", "))
</syntaxhighlight>
{{out}}
<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>
Line 3,843 ⟶ 4,280:
{{trans|Python}}
{{works with|rakudo|2015-10-20}}
<syntaxhighlight lang="raku"
say map { select(@v, $_) }, 1 .. 10;
Line 3,884 ⟶ 4,321:
}
}
}</
{{out}}
<pre>0 1 2 3 4 5 6 7 8 9</pre>
Line 3,890 ⟶ 4,327:
=={{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
Line 3,921 ⟶ 4,358:
L= new+1 /*increase the left half *f the array.*/
end
end /*forever*/</
{{out|output|text= when using the default input:}}
<pre>
Line 3,939 ⟶ 4,376:
===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
Line 3,972 ⟶ 4,409:
end /*forever*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
swap: parse arg _1,_2; parse value @._1 @._2 with @._2 @._1; return /*swap 2 items.*/</
{{out|output|text= is the identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|Ring}}==
<
aList = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
see partition(aList, 9, 4, 2) + nl
Line 3,997 ⟶ 4,434:
next
return storeIndex
</syntaxhighlight>
=={{header|Ruby}}==
<
arr = a.dup # we will be modifying it
loop do
Line 4,017 ⟶ 4,454:
v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
p v.each_index.map { |i| quickselect(v, i) }</
{{out}}
Line 4,023 ⟶ 4,460:
=={{header|Rust}}==
<
fn partition<T: PartialOrd>(a: &mut [T], left: usize, right: usize, pivot: usize) -> usize {
Line 4,073 ⟶ 4,510:
println!("n = {}, nth element = {}", n + 1, b[n]);
}
}</
{{out}}
Line 4,090 ⟶ 4,527:
=={{header|Scala}}==
<
object QuickSelect {
Line 4,109 ⟶ 4,546:
println((0 until v.length).map(quickSelect(v, _)).mkString(", "))
}
}</
{{out}}
Line 4,122 ⟶ 4,559:
The program is written in R7RS-small Scheme. It will run on CHICKEN 5 Scheme if you have the necessary eggs installed and use the "-R r7rs" option.
<
;; Quickselect with random pivot.
;;
Line 4,255 ⟶ 4,692:
((= k 11))
(print-kth > k example-numbers))
(newline)</
{{out}}
Line 4,263 ⟶ 4,700:
=={{header|Sidef}}==
<
var pivot = a.pick
var left = a.grep{|i| i < pivot}
var right = a.grep{|i| i > pivot}
given(
when
case
default
}
}
var v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
say v.range.map{|i| quickselect(v, i)}
{{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
Line 4,292 ⟶ 4,729:
else
x
end</
Usage:
<pre>
Line 4,302 ⟶ 4,739:
=={{header|Swift}}==
<
var r = indices(elements)
while true {
Line 4,321 ⟶ 4,758:
if i < 9 { print(", ") }
}
println()</
{{out}}
Line 4,328 ⟶ 4,765:
=={{header|Tcl}}==
{{trans|Python}}
<
proc swap {list i j} {
upvar 1 $list l
Line 4,377 ⟶ 4,814:
}
}
}</
Demonstrating:
<
foreach i {1 2 3 4 5 6 7 8 9 10} {
puts "$i => [quickselect $v $i]"
}</
{{out}}
<pre>
Line 4,398 ⟶ 4,835:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function quick_select(ByRef s As Variant, k As Integer) As Integer
Dim left As Integer, right As Integer, pos As Integer
Line 4,439 ⟶ 4,876:
Next i
End Sub
</
<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>
Line 4,445 ⟶ 4,882:
{{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]
Line 4,452 ⟶ 4,889:
if (k < 9) System.write(", ")
}
System.print()</
{{out}}
Line 4,458 ⟶ 4,895:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
</pre>
=={{header|XPL0}}==
{{trans|Go}}
<syntaxhighlight lang "XPL0">func QuickSelect(List, Len, K);
int List, Len, K;
int Px, Pv, Last, I, J, T;
[loop [\\partition
Px:= Len/2;
Pv:= List(Px);
Last:= Len-1;
T:= List(Px); List(Px):= List(Last); List(Last):= T;
I:= 0;
for J:= 0 to Last-1 do
[if List(J) < Pv then
[T:= List(I); List(I):= List(J); List(J):= T;
I:= I+1;
];
];
\\select
if I = K then return Pv;
if K < I then Len:= I
else [T:= List(I); List(I):= List(Last); List(Last):= T;
List:= @List(I+1);
Len:= Last - I;
K:= K - (I+1);
];
];
];
int V, K;
[V:= [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
for K:= 0 to 10-1 do
[IntOut(0, QuickSelect(V, 10, K));
ChOut(0, ^ );
];
]</syntaxhighlight>
{{out}}
<pre>
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]);
Line 4,484 ⟶ 4,961:
return(self.fcn(list,pivotIndex+1,right,nth));
}(list.copy(),0,list.len()-1,nth);
}</
<
foreach nth in (list.len()){ println(nth,": ",qselect(list,nth)) }</
{{out}}
<pre>
|