Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
m (fix mxs) |
m (→version 1: added whitepace, changed comments and indentations.) |
||
Line 2,260: | Line 2,260: | ||
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). |
||
<lang rexx>/*REXX program sorts an array using the heapsort |
<lang rexx>/*REXX program sorts an array using the heapsort algorithm. */ |
||
call gen@ /*generate the array elements. */ |
call gen@ /*generate the array elements. */ |
||
call show@ 'before sort' |
call show@ 'before sort' /*show the before array elements*/ |
||
call heapSort |
call heapSort # /*invoke the heap sort. */ |
||
call show@ ' after sort' |
call show@ ' after sort' /*show the after array elements*/ |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────HEAPSORT subroutine─────────────────*/ |
/*──────────────────────────────────HEAPSORT subroutine─────────────────*/ |
||
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 |
||
Line 2,275: | Line 2,275: | ||
return |
return |
||
/*──────────────────────────────────SHUFFLE subroutine──────────────────*/ |
/*──────────────────────────────────SHUFFLE subroutine──────────────────*/ |
||
shuffle: procedure expose @.; parse arg i,n; _=@.i |
shuffle: procedure expose @.; parse arg i,n; _=@.i |
||
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 |
||
if _>=@.j |
if _>=@.j then leave |
||
@.i=@.j; i=j |
@.i=@.j; i=j |
||
end /*while |
end /*while*/ |
||
@.i=_ |
@.i=_ |
||
return |
return |
||
Line 2,295: | Line 2,295: | ||
@.9 = 'eta' ; @.17 = 'omicron' ; @.25 = 'psi' |
@.9 = 'eta' ; @.17 = 'omicron' ; @.25 = 'psi' |
||
@.10 = 'theta' ; @.18 = 'pi' ; @.26 = 'omega' |
@.10 = 'theta' ; @.18 = 'pi' ; @.26 = 'omega' |
||
do highItem=1 while @.highItem\==''; end /*find how many entries. */ |
|||
do #=1 while @.#\==''; end /*find how many entries in list. */ |
|||
#=#-1 /*adjust highItem slightly. */ |
|||
return |
return |
||
/*──────────────────────────────────SHOW@ subroutine────────────────────*/ |
/*──────────────────────────────────SHOW@ subroutine────────────────────*/ |
||
show@: do j=1 for |
show@: do j=1 for # /* [↓] display elements in array.*/ |
||
say 'element' right(j,length( |
say ' element' right(j,length(#)) arg(1)':' @.j |
||
end /*j*/ |
end /*j*/ |
||
say copies(' |
say copies('■', 70) /*show a separator line. */ |
||
return</lang> |
return</lang> |
||
{{out}} using the Greek alphabet for input |
{{out}} using the (default) Greek alphabet for input: |
||
<pre style="height: |
<pre style="height:85ex"> |
||
element 1 before sort: ---modern Greek alphabet letters--- |
element 1 before sort: ---modern Greek alphabet letters--- |
||
element 2 before sort: =================================== |
element 2 before sort: =================================== |
||
element 3 before sort: alpha |
element 3 before sort: alpha |
||
element 4 before sort: beta |
element 4 before sort: beta |
||
element 5 before sort: gamma |
element 5 before sort: gamma |
||
element 6 before sort: delta |
element 6 before sort: delta |
||
element 7 before sort: epsilon |
element 7 before sort: epsilon |
||
element 8 before sort: zeta |
element 8 before sort: zeta |
||
element 9 before sort: eta |
element 9 before sort: eta |
||
element 10 before sort: theta |
element 10 before sort: theta |
||
element 11 before sort: iota |
element 11 before sort: iota |
||
element 12 before sort: kappa |
element 12 before sort: kappa |
||
element 13 before sort: lambda |
element 13 before sort: lambda |
||
element 14 before sort: mu |
element 14 before sort: mu |
||
element 15 before sort: nu |
element 15 before sort: nu |
||
element 16 before sort: xi |
element 16 before sort: xi |
||
element 17 before sort: omicron |
element 17 before sort: omicron |
||
element 18 before sort: pi |
element 18 before sort: pi |
||
element 19 before sort: rho |
element 19 before sort: rho |
||
element 20 before sort: sigma |
element 20 before sort: sigma |
||
element 21 before sort: tau |
element 21 before sort: tau |
||
element 22 before sort: upsilon |
element 22 before sort: upsilon |
||
element 23 before sort: phi |
element 23 before sort: phi |
||
element 24 before sort: chi |
element 24 before sort: chi |
||
element 25 before sort: psi |
element 25 before sort: psi |
||
element 26 before sort: omega |
element 26 before sort: omega |
||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
─────────────────────────────────────────────────────────────────────────────── |
|||
element 1 after sort: ---modern Greek alphabet letters--- |
element 1 after sort: ---modern Greek alphabet letters--- |
||
element 2 after sort: =================================== |
element 2 after sort: =================================== |
||
element 3 after sort: alpha |
element 3 after sort: alpha |
||
element 4 after sort: beta |
element 4 after sort: beta |
||
element 5 after sort: chi |
element 5 after sort: chi |
||
element 6 after sort: delta |
element 6 after sort: delta |
||
element 7 after sort: epsilon |
element 7 after sort: epsilon |
||
element 8 after sort: eta |
element 8 after sort: eta |
||
element 9 after sort: gamma |
element 9 after sort: gamma |
||
element 10 after sort: iota |
element 10 after sort: iota |
||
element 11 after sort: kappa |
element 11 after sort: kappa |
||
element 12 after sort: lambda |
element 12 after sort: lambda |
||
element 13 after sort: mu |
element 13 after sort: mu |
||
element 14 after sort: nu |
element 14 after sort: nu |
||
element 15 after sort: omega |
element 15 after sort: omega |
||
element 16 after sort: omicron |
element 16 after sort: omicron |
||
element 17 after sort: phi |
element 17 after sort: phi |
||
element 18 after sort: pi |
element 18 after sort: pi |
||
element 19 after sort: psi |
element 19 after sort: psi |
||
element 20 after sort: rho |
element 20 after sort: rho |
||
element 21 after sort: sigma |
element 21 after sort: sigma |
||
element 22 after sort: tau |
element 22 after sort: tau |
||
element 23 after sort: theta |
element 23 after sort: theta |
||
element 24 after sort: upsilon |
element 24 after sort: upsilon |
||
element 25 after sort: xi |
element 25 after sort: xi |
||
element 26 after sort: zeta |
element 26 after sort: zeta |
||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
─────────────────────────────────────────────────────────────────────────────── |
|||
</pre> |
</pre> |
||