Pancake Sort in Kotlin

Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.

A pancake number is the minimum number of flips required for a given number of pancakes. The problem was first discussed by American geometer Jacob E. Goodman. It is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence.

Understand the problem

Need to order the pancakes from smallest (top) to largest (bottom), the starting stack can be arranged in any order.
I only can perform flip flipping the entire stack.
To flip a specific pancake to the bottom of the stack, we first must flip it to the top (then flip it again to the bottom).
To order each pancake will require one flip up to the top and one flip down to its final location.

Way of doing :

Find the largest out of order pancake and flip it to the bottom (you may need to flip it to the top of the stack first).
Repeat step one until the stack is ordered.
That's it, a two-step algorithm will work.

Quicksort in kotlin Complete program for Pancake sort in kotlin


class PancakeSort(private val a: IntArray) {
    init {
        for (n in a.size downTo 2) {  // successively reduce size of array by 1
            val index = indexOfMax(n) // find index of largest
            if (index != n - 1) {     // if it's not already at the end
                if (index > 0) {      // if it's not already at the beginning
                    flip(index)       // move largest to beginning
                    println("${a.contentToString()} after flipping first ${index + 1}")
                }
                flip(n - 1)           // move largest to end
                println("${a.contentToString()} after flipping first $n")
            }
        }
    }
 
    private fun indexOfMax(n: Int): Int {
        var index = 0
        for (i in 1 until n) {
            if (a[i] > a[index]) index = i
        }
        return index
    }
 
    private fun flip(index: Int) {
        var i = index
        var j = 0
        while (j < i) {
            val temp = a[j]
            a[j] = a[i]
            a[i] = temp
            j++
            i--
        }
    }
}
 
fun main(args: Array<String>) {
    val a = intArrayOf(7, 6, 9, 2, 4, 8, 1, 3, 5)
    println("${a.contentToString()} initially")
    PancakeSort(a)
}

The output of the Pancake sort in kotlin


[7, 6, 9, 2, 4, 8, 1, 3, 5] initially
[9, 6, 7, 2, 4, 8, 1, 3, 5] after flipping first 3
[5, 3, 1, 8, 4, 2, 7, 6, 9] after flipping first 9
[8, 1, 3, 5, 4, 2, 7, 6, 9] after flipping first 4
[6, 7, 2, 4, 5, 3, 1, 8, 9] after flipping first 8
[7, 6, 2, 4, 5, 3, 1, 8, 9] after flipping first 2
[1, 3, 5, 4, 2, 6, 7, 8, 9] after flipping first 7
[5, 3, 1, 4, 2, 6, 7, 8, 9] after flipping first 3
[2, 4, 1, 3, 5, 6, 7, 8, 9] after flipping first 5
[4, 2, 1, 3, 5, 6, 7, 8, 9] after flipping first 2
[3, 1, 2, 4, 5, 6, 7, 8, 9] after flipping first 4
[2, 1, 3, 4, 5, 6, 7, 8, 9] after flipping first 3
[1, 2, 3, 4, 5, 6, 7, 8, 9] after flipping first 2

In-place merge Sort

Pancake Sort in Kotlin | Data Structures