Sorting algorithms/Heapsort: Difference between revisions

← Older editNewer edit →
Content deleted Content added
m →‎{{header|REXX}}: changed the default array from a modern Greek alphabet to an epichoric alphabet, added/changed comments and whitespace, added whitespace before assignments (that have literals).
Line 3,162: Line 3,162:


Indexing of the array (for this version) starts with   '''1'''   (one),   but can be programmed to start with zero.
Indexing of the array (for this version) starts with   '''1'''   (one),   but can be programmed to start with zero.
<lang rexx>/*REXX program sorts an array (names of modern Greek letters) using a heapsort algorithm*/
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
@.=; @.1='alpha' ; @.6 ="zeta" ; @.11='lambda' ; @.16="pi" ; @.21='phi'
@.=; @.1= 'alpha' ; @.7 = "zeta" ; @.13= 'mu' ; @.19= "qoppa" ; @.25= 'chi'
@.2='beta' ; @.7 ="eta" ; @.12='mu' ; @.17="rho" ; @.22='chi'
@.2= 'beta' ; @.8 = "eta" ; @.14= 'nu' ; @.20= "rho" ; @.26= 'psi'
@.3='gamma' ; @.8 ="theta"; @.13='nu' ; @.18="sigma" ; @.23='psi'
@.3= 'gamma' ; @.9 = "theta" ; @.15= 'xi' ; @.21= "sigma" ; @.27= 'omega'
@.4='delta' ; @.9 ="iota" ; @.14='xi' ; @.19="tau" ; @.24='omega'
@.4= 'delta' ; @.10= "iota" ; @.16= 'omicron'; @.22= "tau"
@.5='epsilon'; @.10="kappa"; @.15='omicron'; @.20="upsilon"
@.5= 'digamma'; @.11= "kappa" ; @.17= 'pi' ; @.23= "upsilon"
do #=1 while @.#\==''; end; #=#-1 /*find # entries.*/
@.6= 'epsilon'; @.12= "lambda"; @.18= 'san' ; @.24= "phi"
do #=1 until @.#==''; end; #=# - 1 /*find # entries.*/
call show "before sort:"
call show "before sort:"
call heapSort #; say copies('▒', 40) /*sort; show sep.*/
call heapSort #; say copies('▒', 40) /*sort; show sep.*/
Line 3,175: Line 3,176:
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
heapSort: procedure expose @.; arg n; do j=n%2 by -1 to 1; call shuffle j,n; end /*j*/
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
do n=n by -1 to 2; _=@.1; @.1=@.n; @.n=_; call shuffle 1, n-1
end /*n*/ /* [↑] swap two elements; and shuffle.*/
end /*n*/ /* [↑] swap two elements; and shuffle.*/
return
return
Line 3,186: Line 3,187:
@.i=$; return
@.i=$; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang>
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang>
'''output''' &nbsp; using the (default) Greek alphabet for input:
{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}
<pre>
<pre>
element 1 before sort: alpha
element 1 before sort: alpha
Line 3,193: Line 3,194:
element 3 before sort: gamma
element 3 before sort: gamma
element 4 before sort: delta
element 4 before sort: delta
element 5 before sort: epsilon
element 5 before sort: digamma
element 6 before sort: zeta
element 6 before sort: epsilon
element 7 before sort: eta
element 7 before sort: zeta
element 8 before sort: theta
element 8 before sort: eta
element 9 before sort: iota
element 9 before sort: theta
element 10 before sort: kappa
element 10 before sort: iota
element 11 before sort: lambda
element 11 before sort: kappa
element 12 before sort: mu
element 12 before sort: lambda
element 13 before sort: nu
element 13 before sort: mu
element 14 before sort: xi
element 14 before sort: nu
element 15 before sort: omicron
element 15 before sort: xi
element 16 before sort: pi
element 16 before sort: omicron
element 17 before sort: rho
element 17 before sort: pi
element 18 before sort: sigma
element 18 before sort: san
element 19 before sort: tau
element 19 before sort: qoppa
element 20 before sort: upsilon
element 20 before sort: rho
element 21 before sort: phi
element 21 before sort: sigma
element 22 before sort: chi
element 22 before sort: tau
element 23 before sort: psi
element 23 before sort: upsilon
element 24 before sort: omega
element 24 before sort: phi
element 25 before sort: chi
element 26 before sort: psi
element 27 before sort: omega
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: alpha
element 1 after sort: alpha
Line 3,218: Line 3,222:
element 3 after sort: chi
element 3 after sort: chi
element 4 after sort: delta
element 4 after sort: delta
element 5 after sort: epsilon
element 5 after sort: digamma
element 6 after sort: eta
element 6 after sort: epsilon
element 7 after sort: gamma
element 7 after sort: eta
element 8 after sort: iota
element 8 after sort: gamma
element 9 after sort: kappa
element 9 after sort: iota
element 10 after sort: lambda
element 10 after sort: kappa
element 11 after sort: mu
element 11 after sort: lambda
element 12 after sort: nu
element 12 after sort: mu
element 13 after sort: omega
element 13 after sort: nu
element 14 after sort: omicron
element 14 after sort: omega
element 15 after sort: phi
element 15 after sort: omicron
element 16 after sort: pi
element 16 after sort: phi
element 17 after sort: psi
element 17 after sort: pi
element 18 after sort: rho
element 18 after sort: psi
element 19 after sort: sigma
element 19 after sort: qoppa
element 20 after sort: tau
element 20 after sort: rho
element 21 after sort: theta
element 21 after sort: san
element 22 after sort: upsilon
element 22 after sort: sigma
element 23 after sort: xi
element 23 after sort: tau
element 24 after sort: zeta
element 24 after sort: theta
element 25 after sort: upsilon
element 26 after sort: xi
element 27 after sort: zeta
</pre>
</pre>


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




'''output''' &nbsp; when using the following for input: &nbsp; <tt> 19 0 -.2 .1 1e5 19 17 -6 789 11 37 </tt>
{{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>
<pre>
element 1 before sort: 19
element 1 before sort: 19
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"