Jump to content

Sorting algorithms/Permutation sort: Difference between revisions

Sorting algorithms/Permutation sort (view source)

Revision as of 20:07, 9 April 2017

284 bytes removed ,  7 years ago
m
→‎{{header|REXX}}: added/changed comments and whitespace, changed indentations, aligned more statements.
(added FreeBASIC)
m (→‎{{header|REXX}}: added/changed comments and whitespace, changed indentations, aligned more statements.)
Line 1,396:
=={{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. */
say copies('▒░', 7075) /*show separator line between displays.*/
call permsetspsets L /*generate items (!) permutations. */
call permSortpSort 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
gen@: @.=; @.1= '---Four_horsemen_of_the_Apocalypse---'
show@: do j=1 for L; say ' element'ele right(j,length(L)wL) arg(1)":" translate(@.j,,'_'); end; return▼
@.2= '====================================='▼
@.3= 'Famine───black_horse'▼
@.4= 'Death───pale_horse'
@.5= 'Pestilence_[Slaughter]───red_horse'
@.6= 'Conquest_[War]───white_horse'
/* [↓] also assign to another array. */▼
do L=1 while @.L\==''; @@.L=@.L; end /* [↓] find number of entries in array*/▼
L=L-1 /*adjust the number of items by one. */▼
return▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
inOrdergen: parse arg@.=; q @.1 = /*see if Q list is in order.*/'---Four_horsemen_of_the_Apocalypse---'
▲ @.2 = '====================================='
_=word(q,1); do j=2 to words(q); x=word(q,j)▼
if x<_ then return 0 @.3 = /*Out of order? Not sorted. */'Famine───black_horse'
_ @.4 =x 'Death───pale_horse'
end /*j*/ @.5 = 'Pestilence_[Slaughter]───red_horse'
do k=1 for #; _=word(#.?,k); @.k=@@._; end /*k*/ @.6 = 'Conquest_[War]───white_horse'
ele=right('element', return 1 15) /*they'reliteral allused infor orderthe finallydisplay.*/
▲ do L=1 while @.L\==''; @@.L=@.L; end; /* [↓] find numberL=L-1; wL=length(L); of entries in array*/return
/*──────────────────────────────────────────────────────────────────────────────────────*/
.permAddisOK: #=#+1; parse arg q do j=1 for N; #.#=#.# !.j; end /*j*/; return /*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
▲ L=L-1 _=x /*adjust the number /*Out of itemsorder? by[↑] one. ¬ sorted*/
▲ @.3= 'Famine───black_horse' end /*j*/
call .permAdd; do whilek=1 .permNext for #; _=word(n#.?,0 k); call @.permAddk=@@._; end /*whilek*/▼
▲ return 1 /*they're [↓]all in alsoorder assign to another arrayfinally. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
.permNextpNext: 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
if i==0 then return 0; do j=i+1 while !.j<!.i; end /*j*/
parse value !.j !.i with !.i !.j
return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
permsetspsets: procedure expose !. # #.; parse arg n,#.; #=0; do f=1 for n; #!.f=0f; end /*f*/
call .pAdd; do while .pNext(n,0); call do f=1 for n.pAdd; !.f=f; end /*fwhile*/
▲ return #
▲ call .permAdd; do while .permNext(n,0); call .permAdd; end /*while*/
return #
/*──────────────────────────────────────────────────────────────────────────────────────*/
permSortpSort: do ?=1 until inOrderisOK($); $= /*find sorted permutation.*/
do m=1 for #; _=word(#.? ,m); $=$ @._; end /*m*/
end /*?*/
return</lang>
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲show@: do j=1 for L; say ' element' right(j,length(L)) arg(1)":" @.j
end /*j*/ /* [↑] display array elements*/
return</lang>
'''output''' &nbsp; using the default (internal) inputs:
<pre>
element 1 before sort: ---Four_horsemen_of_the_ApocalypseFour horsemen of the Apocalypse---
element 2 before sort: =====================================
element 3 before sort: Famine───black_horseFamine───black horse
element 4 before sort: Death───pale_horseDeath───pale horse
element 5 before sort: Pestilence_Pestilence [Slaughter]───red_horse───red horse
element 6 before sort: Conquest_Conquest [War]───white_horse───white horse
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: ---Four_horsemen_of_the_ApocalypseFour horsemen of the Apocalypse---
element 2 after sort: =====================================
element 3 after sort: Conquest_Conquest [War]───white_horse───white horse
element 4 after sort: Death───pale_horseDeath───pale horse
element 5 after sort: Famine───black_horseFamine───black horse
element 6 after sort: Pestilence_Pestilence [Slaughter]───red_horse───red horse
 
Permutation sort took 21 permutations to find the sorted list.
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72833"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information