Step by Step solution about How to resolve the algorithm Sorting algorithms/Patience sort step by step in the Kotlin programming language

Kotlin Patience Sort Implementation

What is Patience Sort?

Patience sort is a sorting algorithm that builds multiple piles of elements, with each pile being sorted in ascending order. Elements are moved between piles until all piles are merged together, resulting in a sorted array.

Source Code Explanation:

1. Function Signature:

fun <T : Comparable<T>> patienceSort(arr: Array<T>)

• Takes an array of comparable elements T that implement the Comparable<T> interface.

2. Initialization:

if (arr.size < 2) return
val piles = mutableListOf<MutableList<T>>()

• Checks if the array has fewer than two elements and returns if so.
• Initializes an empty mutable list of mutable lists, where each inner list represents a pile of elements.

3. Building Piles:

outer@ for (el in arr) {
   for (pile in piles) {
       if (pile.last() > el) {
           pile.add(el)
           continue@outer
       }
   }
   piles.add(mutableListOf(el))
}

• Iterates over all elements in the input array.
• For each element, it iterates over existing piles and adds it to a pile if it's greater than the last element of that pile.
• If no such pile is found, it creates a new pile containing the element.

4. Merging Piles:

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

• Iterates over the input array's indices to fill it with sorted elements.
• Finds the minimum element among the last elements of all piles.
• Adds the minimum element to the input array and removes it from the corresponding pile.
• If a pile becomes empty after removing the minimum element, it's removed from the list of piles.

5. Main Function:

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

   // Array of characters
   val cArr = arrayOf('n', 'o', 'n', 'z', 'e', 'r', 'o', 's', 'u','m')
   patienceSort(cArr)
   println(cArr.contentToString())

   // Array of strings
   val sArr = arrayOf("dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu")
   patienceSort(sArr)
   println(sArr.contentToString())
}

• Calls the patienceSort function on three different arrays: an integer array, a character array, and a string array.
• Prints the sorted contents of the arrays to the console.

Note:

Patience sort has an average time complexity of O(n log n), where n is the number of elements in the array.

// version 1.1.2

fun <T : Comparable<T>> patienceSort(arr: Array<T>) {
    if (arr.size < 2) return
    val piles = mutableListOf<MutableList<T>>()
    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)
    patienceSort(iArr)
    println(iArr.contentToString())
    val cArr = arrayOf('n', 'o', 'n', 'z', 'e', 'r', 'o', 's', 'u','m')
    patienceSort(cArr)
    println(cArr.contentToString())
    val sArr = arrayOf("dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu")
    patienceSort(sArr)
    println(sArr.contentToString())
}