Anonymous user
Sorting algorithms/Heapsort: Difference between revisions
m
→{{header|REXX}}: removed distracting titles within the data, added a version that starts with a list, changed/added whitespace and comments.
No edit summary |
m (→{{header|REXX}}: removed distracting titles within the data, added a version that starts with a list, changed/added whitespace and comments.) |
||
Line 2,694:
===version 1===
This REXX version uses a heapsort to sort elements of an array, the elements can be numbers or strings.
<br>Indexing of the array (for this version) starts with '''1''' (one), but can be programmed to start with zero.
<lang rexx>/*REXX
@.=; @.1='alpha' ; @.6 ='zeta' ; @.11='lambda' ; @.16='pi' ; @.21='phi'
@.5='epsilon'; @.10='kappa'; @.15='omicron'; @.20='upsilon'
do #=1 while @.#\==''; 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. */
/*────────────────────────────────────────────────────────────────────────────*/
heapSort: procedure expose @.; parse 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 /*swap and shuffle.*/
end /*n*/
return
/*────────────────────────────────────────────────────────────────────────────*/
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain the
@.i=
/*────────────────────────────────────────────────────────────────────────────*/
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang>
<pre>
element 1 before sort: alpha
element 2 before sort: beta
element 3 before sort: gamma
element 4 before sort: delta
element 5 before sort: epsilon
element 6 before sort: zeta
element 7 before sort: eta
element 8 before sort: theta
element 9 before sort: iota
element 10 before sort: kappa
element 11 before sort: lambda
element 12 before sort: mu
element 13 before sort: nu
element 14 before sort: xi
element 15 before sort: omicron
element 16 before sort: pi
element 17 before sort: rho
element 18 before sort: sigma
element 19 before sort: tau
element 20 before sort: upsilon
element 21 before sort: phi
element 22 before sort: chi
element 23 before sort: psi
element 24 before sort: omega
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: alpha
element 2 after sort: beta
element 3 after sort: chi
element 4 after sort: delta
element 5 after sort: epsilon
element 6 after sort: eta
element 7 after sort: gamma
element 8 after sort: iota
element 9 after sort: kappa
element 10 after sort: lambda
element 11 after sort: mu
element 12 after sort: nu
element 13 after sort: omega
element 14 after sort: omicron
element 15 after sort: phi
element 16 after sort: pi
element 17 after sort: psi
element 18 after sort: rho
element 19 after sort: sigma
element 20 after sort: tau
element 21 after sort: theta
element 22 after sort: upsilon
element 23 after sort: xi
element 24 after sort: zeta
</pre>
===version 2===
This REXX version creates a stemmed array from a list.
<lang rexx>/*REXX pgm sorts an array (modern Greek alphabet) using a heapsort algorithm. */
g = 'alpha beta gamma delta epsilon zeta eta theta iota kappa lambda mu nu xi',
"omicron pi rho sigma tau upsilon phi chi psi omega" /*adjust # [↓] */
do #=1 for words(g); @.#=word(g,#); end; #=#-1
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 @.; parse 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 /*swap and shuffle.*/
end /*n*/
return
/*────────────────────────────────────────────────────────────────────────────*/
do while i+i<=n;
if k<=n then
@.i=@.j; i=j
end /*while*/
@.i=$; return
/*────────────────────────────────────────────────────────────────────────────*/
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang>
'''output''' is the same as the 1<sup>st</sup> REXX version.
===version
<lang rexx>/* REXX ***************************************************************
* Translated from PL/I
|