Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: added/changed whitespace and comments.)
Line 4,163: Line 4,163:
=={{header|REXX}}==
=={{header|REXX}}==
===version 1===
===version 1===
<lang rexx>/*REXX program sorts a stemmed array using the quicksort algorithm.*/
<lang rexx>/*REXX program sorts a stemmed array using the quicksort algorithm. */
call gen@ /*generate the array elements. */
call gen@ /*generate the elements for the array. */
call show@ 'before sort' /*show before array elements.*/
call show@ 'before sort' /*show the before array elements. */
call quickSort # /*invoke the quicksort routine.*/
call quickSort # /*invoke the quicksort subroutine. */
call show@ ' after sort' /*show after array elements.*/
call show@ ' after sort' /*show the after array elements. */
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────QUICKSORT subroutine────────────────*/
quickSort: procedure expose @. /*access the caller's local var. */
quickSort: procedure expose @. /*access the caller's local variable. */
a.1=1; b.1=arg(1); $=1
a.1=1; b.1=arg(1); $=1


do while $\==0; L=a.$; t=b.$; $=$-1; if t<2 then iterate
do while $\==0; L=a.$; t=b.$; $=$-1; if t<2 then iterate
h=L+t-1
h=L+t-1; ?=L+t%2
if @.h<@.L then if @.?<@.h then do; p=@.h; @.h=@.L; end
?=L+t%2
if @.h<@.L then if @.?<@.h then do; p=@.h; @.h=@.L; end
else if @.?>@.L then p=@.L
else if @.?>@.L then p=@.L
else do; p=@.?; @.?=@.L; end
else do; p=@.?; @.?=@.L; end
else if @.?<@.l then p=@.L
else if @.?<@.l then p=@.L
else if @.?>@.h then do; p=@.h; @.h=@.L; end
else if @.?>@.h then do; p=@.h; @.h=@.L; end
else do; p=@.?; @.?=@.L; end
else do; p=@.?; @.?=@.L; end
j=L+1; k=h
⚫
do forever
j=L+1
do j=j while j<=k & @.j<=p; end /*a tinie-tiny loop.*/
k=h
do k=k by -1 while j <k & @.k>=p; end /*another " " */
⚫
do forever
do j=j while j<=k & @.j<=p; end /*a tinie-tiny loop*/
if j>=k then leave /*segment finished? */
do k=k by -1 while j <k & @.k>=p; end /*another " " */
_=@.j; @.j=@.k; @.k=_ /*swap J&K elements.*/
if j>=k then leave /*segment finished?*/
end /*forever*/
$=$+1
⚫
_=@.j; @.j=@.k; @.k=_ /*swap j&k elements*/
end /*forever*/
k=j-1; @.L=@.k; @.k=p
⚫
if j<=? then do; a.$=j; b.$=h-j+1; $=$+1; a.$=L; b.$=k-L; end
eLse do; a.$=L; b.$=k-L; $=$+1; a.$=j; b.$=h-j+1; end
⚫
end /*whiLe $¬==0*/


k=j-1; @.L=@.k; @.k=p; $=$+1
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
⚫
if j<=? then do; a.$=j; b.$=h-j+1; $=$+1; a.$=L; b.$=k-L; end
eLse do; a.$=L; b.$=k-L; $=$+1; a.$=j; b.$=h-j+1; end
show@: widthH=length(#) /*maximum width of any line of output. */
⚫
do j=1 for # /*display each item in the array. */
⚫
end /*whiLe $¬==0*/
⚫
say 'element' right(j,widthH) arg(1)':' @.j

⚫
end /*j*/
⚫
return
⚫
say copies('▒', maxL + widthH + 22) /*display a separator (between outputs)*/
/*──────────────────────────────────GEN@ subroutine─────────────────────*/
⚫
return
gen@: @.=; maxL=0 /*assign default value for array.*/
/*──────────────────────────────────GEN@ subroutine──────────────────────────────────────────────────────────────────────────────────────────────────────*/
⚫
@.1 = " Rivers that form part of a (USA) state's border " /*this value is adjusted later to include a prefix & suffix.*/
@.2 = '=' /*this value is expanded later. */
gen@: @.=; maxL=0 /*assign default value for array.*/
⚫
@.1 = " Rivers that form part of a (USA) state's border " /*this value is adjusted later to include a prefix & suffix.*/
@.2 = '=' /*this value is expanded later. */
@.3 = "Perdido River Alabama, Florida"
@.3 = "Perdido River Alabama, Florida"
@.4 = "Chattahoochee River Alabama, Georgia"
@.4 = "Chattahoochee River Alabama, Georgia"
Line 4,263: Line 4,268:
@.63 = "Columbia River Oregon, Washington"
@.63 = "Columbia River Oregon, Washington"


do #=1 while @.#\=='' /*find how many entries, and also*/
do #=1 while @.#\=='' /*find how many entries in array, and */
maxL=max(maxL, length(@.#)) /* find the maximum width entry.*/
maxL=max(maxL, length(@.#)) /* also find the maximum width entry.*/
end /*#*/
end /*#*/
#=#-1 /*adjust the highest element #. */
#=#-1 /*adjust the highest element number. */
@.1=centre(@.1, maxL, '-') /*adjust the header information. */
@.1=center(@.1, maxL, '-') /* " " header information. */
@.2=copies(@.2, maxL) /*adjust the header separator. */
@.2=copies(@.2, maxL) /* " " " separator. */
return
/*──────────────────────────────────SHOW@ subroutine────────────────────*/
show@: widthH=length(#) /*maximum width of any line. */
⚫
do j=1 for # /*display each item in the array.*/
⚫
say 'element' right(j,widthH) arg(1)':' @.j
end /*j*/
⚫
say copies('▒', maxL + widthH + 22) /*display a separator line. */
return</lang>
return</lang>
'''output'''
{{out}}
<pre style="height:40ex">
<pre style="height:60ex">
element 1 before sort: ------------------------------------------------ Rivers that form part of a (USA) state's border -------------------------------------------------
element 1 before sort: ------------------------------------------------ Rivers that form part of a (USA) state's border -------------------------------------------------
element 2 before sort: ==================================================================================================================================================
element 2 before sort: ==================================================================================================================================================
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"