Jump to content

Sorting algorithms/Heapsort: Difference between revisions

Sorting algorithms/Heapsort (view source)

Revision as of 21:05, 3 July 2015

848 bytes added ,  8 years ago
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 &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.
<lang rexx>/*REXX programpgm sorts an array (modern usingGreek thealphabet) using a heapsort algorithm. */
@.=; @.1='alpha' ; @.6 ='zeta' ; @.11='lambda' ; @.16='pi' ; @.21='phi'
call gen@ /*generate the array elements. */
call show@ @.2='beta'before sort ; @.7 ='eta' ; @.12='mu' ; /*show the@.17='rho' before array; elements*/ @.22='chi'
call heapSort # @.3='gamma' ; @.8 ='theta'; @.13='nu' ; @.18='sigma' ; /*invoke the heap sort@. */23='psi'
call show@ @.4='delta' after sort; @.9 ='iota' ; @.14='xi' ; /*show@.19='tau' the ; after array elements*/@.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
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 subroutine──────────────────*/
shuffle: procedure expose @.; parse arg i,n; $=@.i /*obtain the _=@.iparent*/
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
/*────────────────────────────────────────────────────────────────────────────*/
return
show: do e=1 for #; say ' element' right(e,length(#)) arg(1) @.e; end; return</lang>
/*──────────────────────────────────GEN@ subroutine─────────────────────*/
gen@:''output''' @.=&nbsp; using @.1='---modernthe (default) Greek alphabet letters---'for /*default; title.*/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
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────SHOW@ subroutine────────────────────*/
show@shuffle: procedure expose @.; parse arg i,n; do j$=1 for #@.i /*obtain [↓]the display elements in array.parent*/
do while i+i<=n; say ' j=i+i; element' right(k=j,length(#)) arg(+1)':' @.j
if k<=n then end if /*@.k>@.j*/ then j=k
say copies('■', 70) if /*show a separator line$>=@.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''' &nbsp; 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 Version 2 3===
<lang rexx>/* REXX ***************************************************************
* Translated from PL/I
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/120652"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information