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

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