Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
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: | Line 2,694: | ||
===version 1=== |
===version 1=== |
||
This REXX version uses a heapsort to sort elements of an array, the elements can be numbers or strings. |
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). |
<br>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 (modern Greek alphabet) using a heapsort algorithm. */ |
||
@.=; @.1='alpha' ; @.6 ='zeta' ; @.11='lambda' ; @.16='pi' ; @.21='phi' |
|||
call gen@ /*generate the array elements. */ |
|||
@.2='beta' ; @.7 ='eta' ; @.12='mu' ; @.17='rho' ; @.22='chi' |
|||
@.3='gamma' ; @.8 ='theta'; @.13='nu' ; @.18='sigma' ; @.23='psi' |
|||
@.4='delta' ; @.9 ='iota' ; @.14='xi' ; @.19='tau' ; @.24='omega' |
|||
@.5='epsilon'; @.10='kappa'; @.15='omicron'; @.20='upsilon' |
|||
exit /*stick a fork in it, we're done.*/ |
|||
do #=1 while @.#\==''; end; #=#-1 /*find # entries*/ |
|||
/*──────────────────────────────────HEAPSORT subroutine─────────────────*/ |
|||
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 |
heapSort: procedure expose @.; parse arg n; do j=n%2 by -1 to 1 |
||
call shuffle j,n |
call shuffle j,n |
||
end /*j*/ |
end /*j*/ |
||
do n=n by -1 to 2 |
do n=n by -1 to 2 |
||
_=@.1; @.1=@.n; @.n=_; call shuffle 1,n-1 /*swap and shuffle.*/ |
_=@.1; @.1=@.n; @.n=_; call shuffle 1,n-1 /*swap and shuffle.*/ |
||
end /*n*/ |
end /*n*/ |
||
return |
return |
||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────SHUFFLE subroutine──────────────────*/ |
|||
shuffle: procedure expose @.; parse arg i,n; |
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain the 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= |
@.i=$; return |
||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
return |
|||
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang> |
|||
/*──────────────────────────────────GEN@ subroutine─────────────────────*/ |
|||
''output''' using the (default) Greek alphabet for input: |
|||
<pre> |
|||
@.2= copies('=', length(@.1)) /*match sep with ↑*/ |
|||
element 1 before sort: alpha |
|||
@.3='alpha' ; @.9 ='eta' ; @.15='nu' ; @.21='tau' |
|||
element 2 before sort: beta |
|||
@.4='beta' ; @.10='theta' ; @.16='xi' ; @.22='upsilon' |
|||
element 3 before sort: gamma |
|||
@.5='gamma' ; @.11='iota' ; @.17='omicron' ; @.23='phi' |
|||
element 4 before sort: delta |
|||
@.6='delta' ; @.12='kappa' ; @.18='pi' ; @.24='chi' |
|||
element 5 before sort: epsilon |
|||
@.7='epsilon' ; @.13='lambd' ; @.19='rho' ; @.25='psi' |
|||
element 6 before sort: zeta |
|||
@.8='zeta' ; @.14='mu' ; @.20='sigma' ; @.26='omega' |
|||
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=== |
|||
do #=1 while @.#\==''; end /*find how many entries in list. */ |
|||
This REXX version creates a stemmed array from a list. |
|||
#=#-1 /*adjust highItem slightly. */ |
|||
<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 |
return |
||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────SHOW@ subroutine────────────────────*/ |
|||
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain the 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 |
|||
return</lang> |
|||
end /*while*/ |
|||
{{out}} using the (default) Greek alphabet for input: |
|||
@.i=$; return |
|||
<pre style="height:85ex"> |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
element 1 before sort: ---modern Greek alphabet letters--- |
|||
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang> |
|||
element 2 before sort: =================================== |
|||
'''output''' is the same as the 1<sup>st</sup> REXX version. |
|||
element 3 before sort: alpha |
|||
element 4 before sort: beta |
|||
element 5 before sort: gamma |
|||
element 6 before sort: delta |
|||
element 7 before sort: epsilon |
|||
element 8 before sort: zeta |
|||
element 9 before sort: eta |
|||
element 10 before sort: theta |
|||
element 11 before sort: iota |
|||
element 12 before sort: kappa |
|||
element 13 before sort: lambda |
|||
element 14 before sort: mu |
|||
element 15 before sort: nu |
|||
element 16 before sort: xi |
|||
element 17 before sort: omicron |
|||
element 18 before sort: pi |
|||
element 19 before sort: rho |
|||
element 20 before sort: sigma |
|||
element 21 before sort: tau |
|||
element 22 before sort: upsilon |
|||
element 23 before sort: phi |
|||
element 24 before sort: chi |
|||
element 25 before sort: psi |
|||
element 26 before sort: omega |
|||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
element 1 after sort: ---modern Greek alphabet letters--- |
|||
element 2 after sort: =================================== |
|||
element 3 after sort: alpha |
|||
element 4 after sort: beta |
|||
element 5 after sort: chi |
|||
element 6 after sort: delta |
|||
element 7 after sort: epsilon |
|||
element 8 after sort: eta |
|||
element 9 after sort: gamma |
|||
element 10 after sort: iota |
|||
element 11 after sort: kappa |
|||
element 12 after sort: lambda |
|||
element 13 after sort: mu |
|||
element 14 after sort: nu |
|||
element 15 after sort: omega |
|||
element 16 after sort: omicron |
|||
element 17 after sort: phi |
|||
element 18 after sort: pi |
|||
element 19 after sort: psi |
|||
element 20 after sort: rho |
|||
element 21 after sort: sigma |
|||
element 22 after sort: tau |
|||
element 23 after sort: theta |
|||
element 24 after sort: upsilon |
|||
element 25 after sort: xi |
|||
element 26 after sort: zeta |
|||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
</pre> |
|||
=== |
===version 3=== |
||
<lang rexx>/* REXX *************************************************************** |
<lang rexx>/* REXX *************************************************************** |
||
* Translated from PL/I |
* Translated from PL/I |