Anonymous user
Quickselect algorithm: Difference between revisions
m
→uses swap subroutine: added/changed comments and whitespace, used a template for the output section.
m (→uses in-line swap: added/changed whitespace and comments, used a template for the output section.) |
m (→uses swap subroutine: added/changed comments and whitespace, used a template for the output section.) |
||
Line 2,268:
===uses swap subroutine===
<lang rexx>/*REXX program sorts a list (which may be numbers) by using the quick select algorithm. */
parse arg list; if list='' then list= 9 8 7 6 5 0 1 2 3 4
say right('list: ', 22) list
#= words(list)
do i=1 for #; @.i= word(list, i)
end /*i*/ /* [↑] #: number of items in the list.*/
say
do j=1 for # /*show 1 ──► # items place and value.*/
say right('item', 20) right(j, length(#))", value: " qSel(1, #, j)
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
qPart: procedure expose @.; parse arg L 1 ?,R,X;
call swap X,R /*swap the two named items (X and R). */
do k=L to R-1 /*process the left side of the list. */
if @.k>xVal then iterate /*when an item > item #X, then skip it.*/
call swap ?,k /*swap the two named items (? and K). */
?= ? +
end /*k*/
call swap R,? /*swap the two named items (R and ?). */
Line 2,291:
qSel: procedure expose @.; parse arg L,R,z; if L==R then return @.L /*only one item?*/
do forever /*keep searching until we're all done. */
new= qPart(L, R, (L+R) % 2)
$= new - L +
if $==z then return @.new /*we're all done with this pivot part. */
else if z<$ then R= new-1
else do; z= z-$
L= new+1
end
end /*forever*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
swap: parse arg _1,_2; parse value @._1 @._2 with @._2 @._1; return /*swap 2 items.*/</lang>
=={{header|Ring}}==
| |||