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