Rosetta Code

Sorting algorithms/Permutation sort: Difference between revisions

Page Discussion

Sorting algorithms/Permutation sort (view source)

Revision as of 08:39, 4 May 2016

1,148 bytes added ,  8 years ago
m
→‎{{header|REXX}}: changed/added comments and whitespace, changed indentations.
(Added Elixir)
m (→‎{{header|REXX}}: changed/added comments and whitespace, changed indentations.)
Line 1,301:
 
=={{header|REXX}}==
<lang rexx>/*REXX program sorts and displays an array using the permutation-sort method. */
call gen@ /*generate the array elements. */
call show@ 'before sort' /*show the before array elements. */
callsay copies('▒', 70) permsets L /*generateshow separator items!line between permutationsdisplays.*/
call permSortpermsets L /*invokegenerate the permutationitems sort. (!) permutations. */
call show@permSort L ' after sort' /*showinvoke the permutation sort. after array elements.*/
gen@:call show@. = ' after sort' /*assignshow default value.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. */
/*──────────────────────────────────GEN@ subroutine─────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲gen@: @. = /*assign default value. */
gen@: @.1=; @.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'
/* [↓] find #also ofassign entriesto inanother array. */
do L=1 while @.L\==''; @@.L=@.L; end /*L [↓] find number of entries in array*/
L=L-1 /*adjust the number of items by one. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────INORDER subroutine──────────────────*/
inOrder: parse arg q /*see if list Q list is in order. */
_=word(q,1); do j=2 to words(q); x=word(q,j)
if x<_ then return 0 /*Out of order? Then notNot sorted. */
_=x
end /*j*/
do k=1 for #; _=word(#.?,k); @.k=@@._; end /*k*/ /*here it is*/
return 1 /*they're all in order finally. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────PERMSETS subroutine─────────────────*/
.permAdd: #=#+1; do fj=1 for nN; ! #.f#=f#.# !.j; end /*j*/; /*f*/return▼
permsets: procedure expose !. # #.; parse arg n,#.; #=0▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲ do f=1 for n; !.f=f; end /*f*/
▲permsets.permNext: procedure expose !. # #.; parse arg n,#.i; #nm=0n-1
call .permAdd /*populate 1st perm*/▼
do k=nm by do-1 while .permNext(n,0);for call .permAddnm; end /*while*/kp=k+1
if !.k<!.kp then do; i=k; leave; end
return #▼
.permNext: procedure expose !.; parse arg n,i; end nm=n-1 /*k*/
do j=i+1 while j<n; parse value !.j !.n with !.n !.j; n=n-1; end▼
do k=nm by -1 for nm; kp=k+1
if !.k<!.kp then do; if i=k=0 then return 0; leave do j=i+1 while !.j<!.i; end /*j*/
parse value !.j !.i with !.i !.j
end /*k*/
end return /*?*/1▼
▲ do j=i+1 while j<n; parse value !.j !.n with !.n !.j; n=n-1; end
/*──────────────────────────────────────────────────────────────────────────────────────*/
if i==0 then return 0; do j=i+1 while !.j<!.i; end /*j*/▼
parsepermsets: valueprocedure expose !. # !#.j; ! parse arg n,#.i; with !.i !.j#=0
▲call .permAdd do f=1 for n; !.f=f; end /*populate 1st permf*/
return 1
.permAdd: #=#+1; do j=1 for N call .permAdd; #.#=# do while .#permNext(n,0); call !.jpermAdd; end /*jwhile*/; return
▲ return #
/*──────────────────────────────────PERMSORT subroutine─────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
permSort: do ?=1 until inOrder($); $= /*look for the sorted permutation*/
permSort: do m?=1 foruntil #inOrder($); $= _=word(#.?,m); $=$ @._;/*find sorted end /*mpermutation.*/
do m=1 for #; _=word(#.? ,m); $=$ @._; end /*m*/
▲ end /*?*/
▲if i==0 then return 0; do j=i+1 while !.j<!.i; end /*j?*/
return
return
/*──────────────────────────────────SHOW@ subroutine────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show@: do j=1 for L /* [↓] display elements in array*/
show@: do j=1 for L; say ' element' right(j,length(L)) arg(1)":" @.j
end /*j*/ /* [↑] display array elements*/
return</lang>▼
say copies('■', 70) /*show a nice separator line. */
'''output''' &nbsp; using the default input(internal) inputs:▼
▲return</lang>
▲'''output''' &nbsp; using the default input:
<pre>
element 1 before sort: ---Four_horsemen_of_the_Apocalypse---
Line 1,363 ⟶ 1,362:
element 5 before sort: Pestilence_[Slaughter]───red_horse
element 6 before sort: Conquest_[War]───white_horse
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
element 1 after sort: ---Four_horsemen_of_the_Apocalypse---
element 2 after sort: =====================================
Line 1,370 ⟶ 1,369:
element 5 after sort: Famine───black_horse
element 6 after sort: Pestilence_[Slaughter]───red_horse
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
 
Permutation sort took 21 permutations to find the sorted list.
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72827"