
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:

O(n logn) sorts
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


Task

Implement a permutation sort, which proceeds by generating the possible permutations
of the input array/list until discovering the sorted one.

Pseudocode:

while not InOrder(list) do
    nextPermutation(list)
done



# This code takes a ridiculously inefficient algorithm and rather futilely
# optimizes one part of it.  Permutations are computed lazily.
 
sorted_copy = (a) ->
  # This returns a sorted copy of an array by lazily generating
  # permutations of indexes and stopping when the indexes yield
  # a sorted array.
  indexes = [0...a.length]
  ans = find_matching_permutation indexes, (permuted_indexes) ->
    new_array = (a[i] for i in permuted_indexes)
    console.log permuted_indexes, new_array
    in_order(new_array)
  (a[i] for i in ans)
 
in_order = (a) ->
  # return true iff array a is in increasing order.
  return true if a.length <= 1
  for i in [0...a.length-1]
    return false if a[i] > a[i+1]
  true
 
get_factorials = (n) ->
  # return an array of the first n+1 factorials, starting with 0!
  ans = [1]
  f = 1
  for i in [1..n]
    f *= i
    ans.push f
  ans
 
permutation = (a, i, factorials) ->
  # Return the i-th permutation of an array by
  # using remainders of factorials to determine
  # elements.
  while a.length > 0
    f = factorials[a.length-1]
    n = Math.floor(i / f)
    i = i % f
    elem = a[n]
    a = a[0...n].concat(a[n+1...])
    elem
  # The above loop gets treated like
  # an array expression, so it returns
  # all the elements.
 
find_matching_permutation = (a, f_match) ->
  factorials = get_factorials(a.length)
  for i in [0...factorials[a.length]]
    permuted_array = permutation(a, i, factorials)
    if f_match permuted_array
      return permuted_array
  null
 
 
do ->
  a = ['c', 'b', 'a', 'd']
  console.log 'input:', a
  ans = sorted_copy a
  console.log 'DONE!'
  console.log 'sorted copy:', ans
 