Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
m (→‎{{header|AppleScript}}: Minor comment correction.)
(→‎{{header|REXX}}: rewrote version 1, elided version 2, renumbered version 3 to version 2.)
Line 3,795: Line 3,795:
=={{header|REXX}}==
=={{header|REXX}}==
===version 1, elements of an array===
===version 1, elements of an array===
This REXX version uses a heapsort to sort elements of an array, the elements can be numbers or character strings   (or a mixture of both).
This REXX version uses a heapsort to sort elements of an array which is constructed from a list of words or numbers,
<br>or a mixture of both.


Indexing of the array (for this version) starts with &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.
Indexing of the array starts with &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
@.=; @.1= 'alpha' ; @.7 = "zeta" ; @.13= 'mu' ; @.19= "qoppa" ; @.25= 'chi'
parse arg x; call init /*use args or default, define @ array.*/
@.2= 'beta' ; @.8 = "eta" ; @.14= 'nu' ; @.20= "rho" ; @.26= 'psi'
call show "before sort:" /*#: the number of elements in array*/
@.3= 'gamma' ; @.9 = "theta" ; @.15= 'xi' ; @.21= "sigma" ; @.27= 'omega'
call heapSort #; say copies('▒', 40) /*sort; then after sort, show separator*/
⚫
call show " after sort:"
@.4= 'delta' ; @.10= "iota" ; @.16= 'omicron'; @.22= "tau"
@.5= 'digamma'; @.11= "kappa" ; @.17= 'pi' ; @.23= "upsilon"
@.6= 'epsilon'; @.12= "lambda"; @.18= 'san' ; @.24= "phi"
⚫
do #=1 until @.#==''; end; #=# - 1 /*find # entries.*/
call show "before sort:"
call heapSort #; say copies('▒', 40) /*sort; show sep.*/
⚫
call show " after sort:"
exit /*stick a fork in it, we're all done. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
⚫
init: _= 'alpha beta gamma delta digamma epsilon zeta eta theta iota kappa lambda mu nu' ,
heapSort: procedure expose @.; arg n; do j=n%2 by -1 to 1; call shuffle j,n; end /*j*/
do n=n by -1 to 2; _=@.1; @.1=@.n; @.n=_; call shuffle 1, n-1
"xi omicron pi san qoppa rho sigma tau upsilon phi chi psi omega"
end /*n*/ /* [↑] swap two elements; and shuffle.*/
if x='' then x= _; #= words(x) /*#: number of words in X*/
⚫
do j=1 for #; @.j= word(x, j); end; return /*assign letters to array*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain parent. */
heapSort: procedure expose @.; arg n; do j=n%2 by -1 to 1; call shuffle j,n; end /*j*/
do while i+i<=n; j=i+i; k=j+1
do n=n by -1 to 2; _= @.1; @.1= @.n; @.n= _; call shuffle 1, n-1
if k<=n then if @.k>@.j then j=k
end /*n*/; return /* [↑] swap two elements; and shuffle.*/
⚫
/*──────────────────────────────────────────────────────────────────────────────────────*/
⚫
if $>=@.j then leave; @.i=@.j; i=j
end /*while*/
shuffle: procedure expose @.; parse arg i,n; $= @.i /*obtain parent.*/
⚫
do while i+i<=n; j= i+i; k= j+1; if k<=n then if @.k>@.j then j= k
@.i=$; return
⚫
if $>=@.j then leave; @.i= @.j; i= j
⚫
end /*while*/; @.i= $; return /*define lowest.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang>
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang>
{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}
{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}
(Shown at three-quarter size.)
<pre>

<pre style="font-size:75%>
element 1 before sort: alpha
element 1 before sort: alpha
element 2 before sort: beta
element 2 before sort: beta
Line 3,882: Line 3,881:
element 27 after sort: zeta
element 27 after sort: zeta
</pre>
</pre>
⚫
{{out|output|text=&nbsp; when using the following for input: &nbsp; &nbsp; <tt> 19 &nbsp;0 &nbsp;-.2 &nbsp;.1 &nbsp;1e5 &nbsp;19 &nbsp;17 &nbsp;-6 &nbsp;789 &nbsp;11 &nbsp;37 </tt>}}
(Shown at three-quarter size.)


<pre style="font-size:75%">
===version 2, elements of a list===
This REXX version creates a stemmed array from a list &nbsp; (it can be numbers or characters, or a mixture of both).
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
parse arg g /*obtain optional arguments from the CL*/
⚫
if g='' then g='alpha beta gamma delta digamma epsilon zeta eta theta iota kappa lambda',
"mu nu xi omicron pi san qoppa rho sigma tau upsilon phi chi psi omega"
⚫
#=words(g); do i=1 for #; @.i=word(g,i); end /*assign to @. */
call show "before sort:"
call heapSort #; say copies('▒', 40) /*sort; show sep*/
call show " after sort:"
exit /*stick a fork in it, we're all done. */
⚫
/*──────────────────────────────────────────────────────────────────────────────────────*/
heapSort: procedure expose @.; arg n; do j=n%2 by -1 to 1; call shuffle j,n; end /*j*/
do n=n by -1 to 2; _=@.1; @.1=@.n; @.n=_; call shuffle 1, n-1
end /*n*/ /* [↑] swap two elements; and shuffle.*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain parent.*/
do while i+i<=n; j=i+i; k=j+1
⚫
if k<=n then if @.k>@.j then j=k
if $>=@.j then leave; @.i=@.j; i=j
end /*while*/
@.i=$; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version when using the default input &nbsp; (an epichoric Greek alphabet).}}


⚫
{{out|output|text=&nbsp; when using the following for input: &nbsp; &nbsp; <tt> 19 &nbsp;0 &nbsp;-.2 &nbsp;.1 &nbsp;1e5 &nbsp;19 &nbsp;17 &nbsp;-6 &nbsp;789 &nbsp;11 &nbsp;37 </tt>}}
<pre>
element 1 before sort: 19
element 1 before sort: 19
element 2 before sort: 0
element 2 before sort: 0
Line 3,938: Line 3,910:
</pre>
</pre>


===version 3===
===version 2===
<lang rexx>/* REXX ***************************************************************
<lang rexx>/* REXX ***************************************************************
* Translated from PL/I
* Translated from PL/I
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"