Sorting algorithms/Heapsort: Difference between revisions
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 |
<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' |
||
@.2= 'beta' ; @.8 = "eta" ; @.14= 'nu' ; @.20= "rho" ; @.26= 'psi' |
|||
@.3= 'gamma' ; @.9 = "theta" ; @.15= 'xi' ; @.21= "sigma" ; @.27= 'omega' |
|||
@.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 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 |
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang> |
||
{{out|output|text= when using the default (epichoric Greek alphabet) 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: |
element 5 before sort: digamma |
||
element 6 before sort: |
element 6 before sort: epsilon |
||
element 7 before sort: |
element 7 before sort: zeta |
||
element 8 before sort: |
element 8 before sort: eta |
||
element 9 before sort: |
element 9 before sort: theta |
||
element 10 before sort: |
element 10 before sort: iota |
||
element 11 before sort: |
element 11 before sort: kappa |
||
element 12 before sort: |
element 12 before sort: lambda |
||
element 13 before sort: |
element 13 before sort: mu |
||
element 14 before sort: |
element 14 before sort: nu |
||
element 15 before sort: |
element 15 before sort: xi |
||
element 16 before sort: |
element 16 before sort: omicron |
||
element 17 before sort: |
element 17 before sort: pi |
||
element 18 before sort: |
element 18 before sort: san |
||
element 19 before sort: |
element 19 before sort: qoppa |
||
element 20 before sort: |
element 20 before sort: rho |
||
element 21 before sort: |
element 21 before sort: sigma |
||
element 22 before sort: |
element 22 before sort: tau |
||
element 23 before sort: |
element 23 before sort: upsilon |
||
element 24 before sort: |
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: |
element 5 after sort: digamma |
||
element 6 after sort: |
element 6 after sort: epsilon |
||
element 7 after sort: |
element 7 after sort: eta |
||
element 8 after sort: |
element 8 after sort: gamma |
||
element 9 after sort: |
element 9 after sort: iota |
||
element 10 after sort: |
element 10 after sort: kappa |
||
element 11 after sort: |
element 11 after sort: lambda |
||
element 12 after sort: |
element 12 after sort: mu |
||
element 13 after sort: |
element 13 after sort: nu |
||
element 14 after sort: |
element 14 after sort: omega |
||
element 15 after sort: |
element 15 after sort: omicron |
||
element 16 after sort: |
element 16 after sort: phi |
||
element 17 after sort: |
element 17 after sort: pi |
||
element 18 after sort: |
element 18 after sort: psi |
||
element 19 after sort: |
element 19 after sort: qoppa |
||
element 20 after sort: |
element 20 after sort: rho |
||
element 21 after sort: |
element 21 after sort: san |
||
element 22 after sort: |
element 22 after sort: sigma |
||
element 23 after sort: |
element 23 after sort: tau |
||
element 24 after sort: |
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 (it can be numbers or characters). |
This REXX version creates a stemmed array from a list (it can be numbers or characters). |
||
<lang rexx>/*REXX |
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/ |
||
parse arg g /*obtain optional |
parse arg g /*obtain optional arguments from the CL*/ |
||
if g='' then g= |
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" |
"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 show "before sort:" |
||
call heapSort #; |
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 |
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang> |
||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version when using the default input (an epichoric Greek alphabet).}} |
|||
{{out|output|text= when using the following for input: <tt> 19 0 -.2 .1 1e5 19 17 -6 789 11 37 </tt>}} |
|||
<pre> |
<pre> |
||
element 1 before sort: 19 |
element 1 before sort: 19 |