Table of content

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 then 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 a 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 takes `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 in kotlin

``````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) {
continue@outer
}
}
}

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())
}``````

The 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]``````
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Subscribe to See Videos

Subscribe to my Youtube channel for new videos : Subscribe Now