
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



/* NetRexx */
options replace format comments java crossref symbols nobinary
 
import java.util.List
import java.util.ArrayList
 
numeric digits 20
 
class RSortingPermutationsort public
 
  properties private static
    iterations
    maxIterations
 
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method permutationSort(vlist = List) public static returns List
    perm = RPermutationIterator(vlist)
    iterations = 0
    maxIterations = RPermutationIterator.factorial(vlist.size())
    loop while perm.hasNext()
      iterations = iterations + 1
      pl = List perm.next()
      if isSorted(pl) then leave
      else pl = null
      end
    return pl
 
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method isSorted(ss = List) private static returns boolean
    status = isTrue
    loop ix = 1 while ix < ss.size()
      vleft  = Rexx ss.get(ix - 1)
      vright = Rexx ss.get(ix)      
      if vleft.datatype('N') & vright.datatype('N')
      then vtest = vleft > vright  -- For numeric types we must use regular comparison.
      else vtest = vleft >> vright -- For non-numeric/mixed types we must do strict comparison.
      if vtest then do
        status = isFalse
        leave ix
        end
      end ix
    return status
 
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method runSample(arg) private static
    placesList = -
        "UK  London,     US  New York,   US  Boston,     US  Washington" -
        "UK  Washington, US  Birmingham, UK  Birmingham, UK  Boston"
    anotherList = 'Alpha, Beta, Gamma, Beta'
    reversed = '7, 6, 5, 4, 3, 2, 1'
    unsorted = '734, 3, 1, 24, 324, -1024, -666, -1, 0, 324, 99999999'
    lists = [makeList(placesList), makeList(anotherList), makeList(reversed), makeList(unsorted)]
    loop il = 0 while il < lists.length
      vlist = lists[il]
      say vlist
      runtime = System.nanoTime()
      rlist = permutationSort(vlist)
      runtime = System.nanoTime() - runtime
      if rlist \= null then say rlist
      else say 'sort failed'
      say 'This permutation sort of' vlist.size() 'elements took' iterations 'passes (of' maxIterations') to complete. \-'
      say 'Elapsed time:' (runtime / 10 ** 9)'s.'
      say
      end il
    return
 
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method makeList(in) public static returns List
    lst = ArrayList()
    loop while in > ''
      parse in val ',' in
      lst.add(val.strip())
      end
    return lst
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method main(args = String[]) public static
    runSample(Rexx(args))
    return
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method isTrue() public static returns boolean
    return (1 == 1)
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  method isFalse() public static returns boolean
    return (1 == 0)
 