Rosetta Code

Sorting algorithms/Heapsort: Difference between revisions

Page Discussion

Sorting algorithms/Heapsort (view source)

Revision as of 15:25, 17 May 2020

2,408 bytes removed ,  4 years ago
→‎{{header|REXX}}: rewrote version 1, elided version 2, renumbered version 3 to version 2.
m (→‎{{header|AppleScript}}: Minor comment correction.)
(→‎{{header|REXX}}: rewrote version 1, elided version 2, renumbered version 3 to version 2.)
Line 3,795:
=={{header|REXX}}==
===version 1, elements of an array===
This REXX version uses a heapsort to sort elements of an array, thewhich elementsis canconstructed befrom numbersa orlist characterof stringswords   (or a mixture ofnumbers, both).
<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.
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
@.=parse arg x; @.1= 'alpha' ; @.7 = "zeta" ; @.13= 'mu' call init ; @.19= "qoppa" ; /*use args or default, define @.25= 'chi'array.*/
call show @.2= 'beta'"before sort:" ; @.8 = "eta" ; @.14= 'nu' ; @.20=/*#: "rho" the number ;of elements @.26=in 'psi'array*/
call heapSort @.3= 'gamma' #; @.9 = "theta" ; say @.15= copies('xi▒', 40) /*sort; then @.21=after "sigma"sort, show ; @.27= 'omega'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. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
ifinit: g_='' then g='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; "xi omicron pi _=@.1;san qoppa rho @.1=@.n;sigma tau upsilon @.n=_;phi chi psi call shuffle 1, n-1omega"
if x='' then x= _; end /*n*/ #= words(x) /*#: [↑]number of swap two elements;words andin shuffle.X*/
#=words(g); do ij=1 for #; @.ij= word(gx,i j); end; return /*assign letters to @. array*/▼
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
shuffleheapSort: procedure expose @.; parse arg i,n; do $j=@.i n%2 by -1 to 1; call shuffle j,n; end /*obtain parent. j*/
do n=n by -1 to 2; _= @.1; @.1= do while i+i<=@.n; @.n= _; j=i+i;call shuffle 1, k=j+n-1
end /*n*/; return /* [↑] swap two elements; ifand k<=n then if @shuffle.k>@.j then j=k*/
/*──────────────────────────────────────────────────────────────────────────────────────*/▼
if $>=@.j then leave; @.i=@.j; i=j▼
shuffle: procedure expose @.; parse arg i,n; $= @.i end /*whileobtain 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= do$; #=1 until @.#==''; end; return #=# - 1 /*find #define entrieslowest.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
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:}}
(Shown at three-quarter size.)
<pre>
 
<pre style="font-size:75%>
element 1 before sort: alpha
element 2 before sort: beta
Line 3,882 ⟶ 3,881:
element 27 after sort: zeta
</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 2 before sort: 0
Line 3,938 ⟶ 3,910:
</pre>
 
===version 32===
<lang rexx>/* REXX ***************************************************************
* Translated from PL/I
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/120714"