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

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

Recommended Reading

• In-place merge Sort
• Insertion Sort
• Selection Sort
• Kotlin Basics
• invoke Operator
• Operators in Kotlin
• Abstract Classes
• Koltin Annotations
• Apache Commons CSV Integration
• While Loop in Kotlin
• Excel Files
• Kotlin Generics with Classes
• Check File existence
• let in kotlin