
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



      DIM test(9)
      test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1
 
      perms% = 0
      WHILE NOT FNsorted(test())
        perms% += 1
        PROCnextperm(test())
      ENDWHILE
      PRINT ;perms% " permutations required to sort "; DIM(test(),1)+1 " items."
      END
 
      DEF PROCnextperm(a())
      LOCAL last%, maxindex%, p%
      maxindex% = DIM(a(),1)
      IF maxindex% < 1 THEN ENDPROC
      p% = maxindex%-1
      WHILE a(p%) >= a(p%+1)
        p% -= 1
        IF p% < 0 THEN
          PROCreverse(a(), 0, maxindex%)
          ENDPROC
        ENDIF
      ENDWHILE
      last% = maxindex%
      WHILE a(last%) <= a(p%)
        last% -= 1
      ENDWHILE
      SWAP a(p%), a(last%)
      PROCreverse(a(), p%+1, maxindex%)
      ENDPROC
 
      DEF PROCreverse(a(), first%, last%)
      WHILE first% < last%
        SWAP a(first%), a(last%)
        first% += 1
        last% -= 1
      ENDWHILE
      ENDPROC
 
      DEF FNsorted(d())
      LOCAL I%
      FOR I% = 1 TO DIM(d(),1)
        IF d(I%) < d(I%-1) THEN = FALSE
      NEXT
      = TRUE