Rosetta Code

Quickselect algorithm: Difference between revisions

Page Discussion

Quickselect algorithm (view source)

Revision as of 12:16, 29 January 2024

16,157 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
(Added XPL0 example.)
m (→‎{{header|Wren}}: Minor tidy)
 
(5 intermediate revisions by 3 users not shown)
Line 56:
<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>
 
Line 699 ⟶ 930:
{{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}}==
 
Line 2,077 ⟶ 2,505:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
funcproc qselect k . list[] res .
#
subr partition
mid = left
for i = left + 1 to right
if list[i] < list[left]
mid += 1
swap list[i] list[mid]
.
.
swap list[left] list[mid]
.
.
swap list[left] list[mid]
left = 1
.
left right = 1len list[]
while left < right
right = len list[]
partition
while left < right
call partition if mid < k
if left = mid <+ k1
left =elif mid +> 1k
elif right = mid >- k1
right = mid - 1else
left = right
else
left = right.
.
res = list[k]
.
res = list[k]
.
d[] = [ 9 8 7 6 5 0 1 2 3 4 ]
for i = 1 to len d[]
call qselect i d[] r
print r
.
</syntaxhighlight>
Line 4,273 ⟶ 4,701:
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func quickselect(a, k) {
var pivot = a.pick;
var left = a.grep{|i| i < pivot};
var right = a.grep{|i| i > pivot};
 
given(var l = left.len) { |l|
when (k) { pivot }
case (k < l) { __FUNC__(left, k) }
default { __FUNC__(right, k - l - 1) }
}
}
 
var v = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4];
say v.range.map{|i| quickselect(v, i)};</syntaxhighlight>
{{out}}
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>
Line 4,454 ⟶ 4,882:
{{libheader|Wren-sort}}
The Find.quick method in the above module implements the quickselect algorithm.
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Find
 
var a = [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340951...352194"