Sorting algorithms/Permutation sort: Difference between revisions
Content added Content deleted
(Added Elixir) |
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
||
Line 1,301: | Line 1,301: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
<lang rexx>/*REXX program sorts an array using the permutation-sort method. */ |
<lang rexx>/*REXX program sorts and displays an array using the permutation-sort method. */ |
||
call gen@ /*generate the array elements. */ |
call gen@ /*generate the array elements. */ |
||
call show@ |
call show@ 'before sort' /*show the before array elements. */ |
||
say copies('▒', 70) /*show separator line between displays.*/ |
|||
call |
call permsets L /*generate items (!) permutations. */ |
||
call |
call permSort L /*invoke the permutation sort. */ |
||
⚫ | |||
say; say 'Permutation sort took' ? "permutations to find the sorted list." |
say; say 'Permutation sort took' ? "permutations to find the sorted list." |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────GEN@ subroutine─────────────────────*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
@. |
gen@: @.=; @.1= '---Four_horsemen_of_the_Apocalypse---' |
||
@.2 |
@.2= '=====================================' |
||
@.3 |
@.3= 'Famine───black_horse' |
||
@.4 |
@.4= 'Death───pale_horse' |
||
@.5 |
@.5= 'Pestilence_[Slaughter]───red_horse' |
||
@.6 |
@.6= 'Conquest_[War]───white_horse' |
||
/*[↓] |
/* [↓] also assign to another array. */ |
||
do L=1 while @.L\==''; |
do L=1 while @.L\==''; @@.L=@.L; end /* [↓] find number of entries in array*/ |
||
L=L-1 /*adjust number of items by one. */ |
L=L-1 /*adjust the number of items by one. */ |
||
return |
return |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────INORDER subroutine──────────────────*/ |
|||
inOrder: parse arg q /*see if |
inOrder: parse arg q /*see if Q list is in order.*/ |
||
_=word(q,1); do j=2 to words(q); |
_=word(q,1); do j=2 to words(q); x=word(q,j) |
||
if x<_ then return 0 /*Out of order? |
if x<_ then return 0 /*Out of order? Not sorted. */ |
||
_=x |
_=x |
||
end /*j*/ |
end /*j*/ |
||
do k=1 for #; _=word(#.?,k); @.k=@@._; end /*k |
do k=1 for #; _=word(#.?,k); @.k=@@._; end /*k*/ |
||
return 1 /*they're all in order finally |
return 1 /*they're all in order finally*/ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────PERMSETS subroutine─────────────────*/ |
|||
⚫ | |||
⚫ | |||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
do k=nm by -1 for nm; kp=k+1 |
|||
if !.k<!.kp then do; i=k; leave; end |
|||
⚫ | |||
end /*k*/ |
|||
⚫ | |||
do k=nm by -1 for nm; kp=k+1 |
|||
if i==0 then return 0; do j=i+1 while !.j<!.i; end /*j*/ |
|||
parse value !.j !.i with !.i !.j |
|||
end /*k*/ |
|||
⚫ | |||
⚫ | |||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
permsets: procedure expose !. # #.; parse arg n,#.; #=0 |
|||
⚫ | |||
return 1 |
|||
call .permAdd; do while .permNext(n,0); call .permAdd; end /*while*/ |
|||
⚫ | |||
/*──────────────────────────────────PERMSORT subroutine─────────────────*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
permSort: do ?=1 until inOrder($); $= /*look for the sorted permutation*/ |
|||
permSort: do ?=1 until inOrder($); $= /*find sorted permutation.*/ |
|||
do m=1 for #; _=word(#.? ,m); $=$ @._; end /*m*/ |
|||
⚫ | |||
⚫ | |||
return |
|||
return |
|||
/*──────────────────────────────────SHOW@ subroutine────────────────────*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
show@: do j=1 for L /* [↓] display elements in array*/ |
|||
say ' element' right(j,length(L)) arg(1)":" @.j |
show@: do j=1 for L; say ' element' right(j,length(L)) arg(1)":" @.j |
||
end /*j*/ |
end /*j*/ /* [↑] display array elements*/ |
||
⚫ | |||
say copies('■', 70) /*show a nice separator line. */ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
<pre> |
<pre> |
||
element 1 before sort: ---Four_horsemen_of_the_Apocalypse--- |
element 1 before sort: ---Four_horsemen_of_the_Apocalypse--- |
||
Line 1,363: | Line 1,362: | ||
element 5 before sort: Pestilence_[Slaughter]───red_horse |
element 5 before sort: Pestilence_[Slaughter]───red_horse |
||
element 6 before sort: Conquest_[War]───white_horse |
element 6 before sort: Conquest_[War]───white_horse |
||
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ |
|||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
element 1 after sort: ---Four_horsemen_of_the_Apocalypse--- |
element 1 after sort: ---Four_horsemen_of_the_Apocalypse--- |
||
element 2 after sort: ===================================== |
element 2 after sort: ===================================== |
||
Line 1,370: | Line 1,369: | ||
element 5 after sort: Famine───black_horse |
element 5 after sort: Famine───black_horse |
||
element 6 after sort: Pestilence_[Slaughter]───red_horse |
element 6 after sort: Pestilence_[Slaughter]───red_horse |
||
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ |
|||
Permutation sort took 21 permutations to find the sorted list. |
Permutation sort took 21 permutations to find the sorted list. |