Rosetta Code

Sorting algorithms/Permutation sort: Difference between revisions

Page Discussion

Sorting algorithms/Permutation sort (view source)

Revision as of 00:43, 31 August 2017

255 bytes removed ,  6 years ago
m
→‎{{header|REXX}}: added/changed comments and whitespace, brought a function in-line, aligned some statements, used template for output.
(Added Julia language)
m (→‎{{header|REXX}}: added/changed comments and whitespace, brought a function in-line, aligned some statements, used template for output.)
Line 1,479:
call show 'before sort' /*show the before array elements. */
say copies('░', 75) /*show separator line between displays.*/
call psetspSort L L /*generateinvoke the permutation sort. items (!) permutations. */
call pSort L /*invoke the permutation sort. */▼
call show ' after sort' /*show the after array elements. */
say; say 'Permutation sort took ' ? " permutations to find the sorted list."
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
.pAdd: #=#+1; do j=1 for N; #.#=#.# !.j; end; return /*add a end; returnpermutation.*/
show: do j=1 for L; say ele@e right(j,wL) arg(1)":" translate(@.j,,'_'); end; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen: @.=; @.1 = '---Four_horsemen_of_the_Apocalypse---'
@.2 = '====================================='
@.3 = 'Famine───black_horse'
@.4 = 'Death───pale_horse'
@.5 = 'Pestilence_[Slaughter]───red_horse'
@.6 = 'Conquest_[War]───white_horse'
ele@e=right('element', 15) /*literal used for the display.*/
do L=1 while @.L\==''; @@.L=@.L; end; L=L-1; wL=length(L); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
isOKisOrd: parse arg q /*see if Q list is in order. */
_=word(q, 1); do j=2 to words(q); x=word(q, j); if x<_ then return 0; _=x
end _=x /*j*/ /* [↑] /*Out of order? [↑] ¬ sorted*/
do k=1 for #; _=word(#.?, k); @.k=@@._; end /*k*/; end return 1 /*jin order.*/
do k=1 for #; _=word(#.?, k); @.k=@@._; end /*k*/
return 1 /*they're all in order finally.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
.pNext: procedure expose !.; parse arg n,i; nm=n-1
do k=nm by -1 for nm; kp=k+1
if !.k<!.kp then do; i=k; leave; end
end /*k*/ /* [↓] swap two array elements*/
do j=i+1 while j<n; parse value !.j !.n with !.n !.j; n=n-1; end /*j*/
if i==0 then return 0; do j=i+1 while !.j<!.i; end /*j0: indicates no more perms. */
parse valuedo j=i+1 while !.j <!.i; end with /*j*/ !.i !.j /*search perm for a lower value*/
parse value !.j !.i with !.i !.j /*swap two values in !. array.*/
return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
psetspSort: procedure expose !. # #.; parse arg n,#.; #=0; do f=1 for n; !.f=f; end /*fgenerate L items (!) permutations.*/
call .pAdd; do whilef=1 for .pNext(n,0); call !.pAddf=f; end /*whilef*/
call .pAdd; do while .pNext(n, 0); call .pAdd; end /*while*/
return #
▲call pSort L do ?=1 until isOrd($); $= /*invoke the permutation sort. /*find perm.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
pSort: do ?=1 until isOK($); do $m=1 for #; _=word(#.?, m); $=$ @._; end /*findm*/ sorted permutation./*build list*/
end do m=1 for #; _=word(#.? ,m); $=$ @._; end /*m?*/
end /*?*/
return</lang>
'''{{out|output''' |text=&nbsp; when using the default (internal) inputs:}}
<pre>
element 1 before sort: ---Four horsemen of the Apocalypse---
Line 1,537 ⟶ 1,534:
element 6 after sort: Pestilence [Slaughter]───red horse
 
Permutation sort took 21 permutations to find the sorted list.
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72837"