
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



// version 1.1.2
 
fun <T : Comparable<T>> isSorted(list: List<T>): Boolean {
    val size = list.size
    if (size < 2) return true
    for (i in 1 until size) {
        if (list[i] < list[i - 1]) return false
    }
    return true
}
 
fun <T : Comparable<T>> permute(input: List<T>): List<List<T>> {
    if (input.size == 1) return listOf(input)
    val perms = mutableListOf<List<T>>()
    val toInsert = input[0]
    for (perm in permute(input.drop(1))) {
        for (i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, toInsert)
            perms.add(newPerm)
        }
    }
    return perms
}
 
fun <T : Comparable<T>> permutationSort(input: List<T>): List<T> {
    if (input.size == 1) return input
    val toInsert = input[0]
    for (perm in permute(input.drop(1))) {
        for (i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, toInsert)
            if (isSorted(newPerm)) return newPerm
        }
    }
    return input
}
 
fun main(args: Array<String>) {
    val input = listOf('d', 'b', 'e', 'a', 'f', 'c')
    println("Before sorting : $input")
    val output = permutationSort(input)
    println("After sorting  : $output")
    println()
    val input2 = listOf("first", "second", "third", "fourth", "fifth", "sixth")
    println("Before sorting : $input2")
    val output2 = permutationSort(input2)
    println("After sorting  : $output2")
}