Sorting algorithms/Permutation sort: Difference between revisions
No edit summary |
|||
Line 5: | Line 5: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
Since < |
Since <tt>next_permutation</tt> already returns whether the resulting sequence is sorted, the code is quite simple: |
||
<cpp> |
<lang cpp> |
||
#include <algorithm> |
#include <algorithm> |
||
Line 18: | Line 18: | ||
} |
} |
||
} |
} |
||
</ |
</lang> |
||
=={{header|D}}== |
=={{header|D}}== |
||
<d>module permsort ; |
<lang d>module permsort ; |
||
import std.stdio ; |
import std.stdio ; |
||
Line 63: | Line 63: | ||
writefln("%s", permsort(["rosetta"])) ; // test with one element |
writefln("%s", permsort(["rosetta"])) ; // test with one element |
||
writefln("%s", permsort(cast(int[])[])) ; // test empty array |
writefln("%s", permsort(cast(int[])[])) ; // test empty array |
||
}</ |
}</lang> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 109: | Line 109: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Like the Haskell version, except not evaluated lazily. So it always computes all the permutations, before searching through them for a sorted one; which is more expensive than necessary; unlike the Haskell version, which stops generating at the first sorted permutation. |
Like the Haskell version, except not evaluated lazily. So it always computes all the permutations, before searching through them for a sorted one; which is more expensive than necessary; unlike the Haskell version, which stops generating at the first sorted permutation. |
||
<ocaml>let rec sorted = function |
<lang ocaml>let rec sorted = function |
||
| e1 :: e2 :: r -> e1 <= e2 && sorted (e2 :: r) |
| e1 :: e2 :: r -> e1 <= e2 && sorted (e2 :: r) |
||
| _ -> true |
| _ -> true |
||
Line 121: | Line 121: | ||
| h :: t -> List.concat (List.map (fun t' -> insert h t') (permute t)) |
| h :: t -> List.concat (List.map (fun t' -> insert h t') (permute t)) |
||
let permutation_sort l = List.find sorted (permute l)</ |
let permutation_sort l = List.find sorted (permute l)</lang> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Line 136: | Line 136: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
<scheme> |
<lang scheme> |
||
(define (insertions e list) |
(define (insertions e list) |
||
(if (null? list) |
(if (null? list) |
||
Line 162: | Line 162: | ||
(car permutations) |
(car permutations) |
||
(loop (cdr permutations))))) |
(loop (cdr permutations))))) |
||
</ |
</lang> |
Revision as of 15:44, 3 February 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Permutation sort.
Pseudocode:
while not InOrder(list) do nextPermutation(list);
C++
Since next_permutation already returns whether the resulting sequence is sorted, the code is quite simple:
<lang cpp>
- include <algorithm>
template<typename ForwardIterator>
void permutation_sort(ForwardIterator begin, ForwardIterator end)
{
while (std::next_permutation(begin, end)) { // -- this block intentionally left empty -- }
} </lang>
D
<lang d>module permsort ; import std.stdio ;
bool isSorted(T)(inout T[] a) { // test if a is already sorted
if(a.length <= 1) return true ; // 1-elemented/empty array is defined as sorted for(int i = 1 ; i < a.length ; i++) if(a[i] < a[i-1]) return false ; return true ;
}
Permutator!(T) Perm(T)(T[] x) { return Permutator!(T)(x) ; } struct Permutator(T) { // permutation iterator
T[] s ; alias int delegate(inout T[]) DG ; void swap(int i, int j) { T tmp = s[i] ; s[i] = s[j] ; s[j] = tmp ; } int opApply(DG dg) { return perm(0, s.length, dg) ; } int perm(int breaked, int n, DG dg) { if(breaked) return breaked ; else if(n <= 1) breaked = dg(s) ; else { for(int i = 0 ; i < n ; i++) { if((breaked = perm(breaked, n - 1, dg)) != 0) break ; if(0 == (n % 2)) swap(i, n-1) ; else swap(0, n-1) ; } } return breaked ; }
}
T[] permsort(T)(T[] s) {
foreach( p ; Perm(s)) if(isSorted(p)) return p.dup ; assert(false, "Should not be here") ;
}
void main() {
auto p = [2,7,4,3,5,1,0,9,8,6] ; writefln("%s", permsort(p)) ; writefln("%s", p) ; // sort is in place writefln("%s", permsort(["rosetta"])) ; // test with one element writefln("%s", permsort(cast(int[])[])) ; // test empty array
}</lang>
Haskell
import Control.Monad permutationSort l = head $ do p <- permute l if sorted p then return p else mzero sorted (e1 : e2 : r) = e1 <= e2 && sorted (e2 : r) sorted _ = True permute [] = return [] permute (h:t) = do { t' <- permute t ; insert h t' } insert e [] = return [e] insert e l@(h : t) = return (e : l) `mplus` do { t' <- insert e t ; return (h : t') }
Icon
Partly from here
procedure do_permute(l, i, n) if i >= n then return l else suspend l[i to n] <-> l[i] & do_permute(l, i+1, n) end procedure permute(l) suspend do_permute(l, 1, *l) end procedure sorted(l) local i if (i := 2 to *l & l[i] >= l[i-1]) then return &fail else return 1 end procedure main() local l l := [6,3,4,5,1] |( l := permute(l) & sorted(l)) \1 & every writes(" ",!l) end
OCaml
Like the Haskell version, except not evaluated lazily. So it always computes all the permutations, before searching through them for a sorted one; which is more expensive than necessary; unlike the Haskell version, which stops generating at the first sorted permutation. <lang ocaml>let rec sorted = function
| e1 :: e2 :: r -> e1 <= e2 && sorted (e2 :: r) | _ -> true
let rec insert e = function
| [] -> e | h :: t as l -> (e :: l) :: List.map (fun t' -> h :: t') (insert e t)
let rec permute = function
| [] -> [[]] | h :: t -> List.concat (List.map (fun t' -> insert h t') (permute t))
let permutation_sort l = List.find sorted (permute l)</lang>
Prolog
permutation_sort(L,S) :- permutation(L,S), sorted(S). sorted([]). sorted([_]). sorted([X,Y|ZS]) :- X =< Y, sorted([Y|ZS]). permutation([],[]). permutation([X|XS],YS) :- permutation(XS,ZS), select(X,YS,ZS).
Scheme
<lang scheme> (define (insertions e list)
(if (null? list) (cons (cons e list) list) (cons (cons e list) (map (lambda (tail) (cons (car list) tail)) (insertions e (cdr list))))))
(define (permutations list)
(if (null? list) (cons list list) (apply append (map (lambda (permutation) (insertions (car list) permutation)) (permutations (cdr list))))))
(define (sorted? list)
(cond ((null? list) #t) ((null? (cdr list)) #t) ((<= (car list) (cadr list)) (sorted? (cdr list))) (else #f)))
(define (permutation-sort list)
(let loop ((permutations (permutations list))) (if (sorted? (car permutations)) (car permutations) (loop (cdr permutations)))))
</lang>