Patience Sort in Kotlin | Data Structures

Patience sort is just another O(n lg n) sorting algorithm (it actually depends on implementation). If you have played solitaire before, it's kind of similar. The algorithm maintains a list of stacks each of which is sorted in decreasing order (tail to head). The numbers are inserted incrementally.

To insert a number x, find the leftmost stack whose top element is larger than x and push x onto it. If no such stack exists create a new one at the end and push x onto it.

Notice that the way we insert numbers implies that top elements of the stacks are sorted in increasing order so the length of the longest increasing subsequence is just the number of piles at the end.

Once all numbers are inserted and the piles are ready, we'll repeatedly find the minimum number and write it to output. The stack from which we took the number must be inserted in a new position now so that the top elements of the stacks are sorted again. This can be done by using a heap to store the stacks.

If you simply scan the top elements to find the minimum and use no fancy data structures, the algorithm take O(n sqrt(n)) which is not bad for small n.

So this sorts the list of numbers and gives you the length of the LIS (and with some augmentation gives you a LIS).

Selection Sort


fun patienceSort(arr: Array<Int>) {
    if (arr.size < 2) return
    val piles = mutableListOf<MutableList<Int>>()
    outer@ for (el in arr) {
        for (pile in piles) {
            if (pile.last() > el) {
                pile.add(el)
                continue@outer
            }
        }
        piles.add(mutableListOf(el))
    }

    for (i in 0 until arr.size) {
        var min = piles[0].last()
        var minPileIndex = 0
        for (j in 1 until piles.size) {
            if (piles[j].last() < min) {
                min = piles[j].last()
                minPileIndex = j
            }
        }
        arr[i] = min
        val minPile = piles[minPileIndex]
        minPile.removeAt(minPile.lastIndex)
        if (minPile.size == 0) piles.removeAt(minPileIndex)
    }
}

fun main(args: Array<String>) {
    val iArr = arrayOf(4, 65, 2, -31, 0, 99, 83, 782, 1)
    println(iArr.contentToString())
    patienceSort(iArr)
    println(iArr.contentToString())
}


Output of the Patience sort in Kotlin


[4, 65, 2, -31, 0, 99, 83, 782, 1]
[-31, 0, 1, 2, 4, 65, 83, 99, 782]			

Comb Sort

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group