33 lines
2.7 KiB
Rexx
33 lines
2.7 KiB
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 /*Not given? Use default.*/
|
|
say right('list: ', 22) list
|
|
#=words(list)
|
|
do i=1 for #; @.i=word(list, i) /*assign all the items ──► @. (array). */
|
|
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; xVal=@.X
|
|
parse value @.X @.R with @.R @.X /*swap the two names 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.*/
|
|
parse value @.? @.k with @.k @.? /*swap the two named items (? and K). */
|
|
?=?+1 /*bump the item number (point to next).*/
|
|
end /*k*/
|
|
parse value @.R @.? with @.? @.R /*swap the two named items (R and ?). */
|
|
return ? /*return the item number to invoker. */
|
|
/*──────────────────────────────────────────────────────────────────────────────────────*/
|
|
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) /*partition the list into roughly ½. */
|
|
$=new-L+1 /*calculate pivot distance less L+1. */
|
|
if $==z then return @.new /*we're all done with this pivot part. */
|
|
else if z<$ then R=new-1 /*decrease the right half of the array.*/
|
|
else do; z=z-$ /*decrease the distance. */
|
|
L=new+1 /*increase the left half *f the array.*/
|
|
end
|
|
end /*forever*/
|