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
Recommended Reading
About Author
This article is written by Pavan, who is serving notice period in an MNC, Bangalore. He thought, let the articles speak rather than his image. He is also the same person who created the reporter for Protractor Jasmine
