You are in front of a stack of pancakes of different diameter. Unfortunately, yo

Question

You are in front of a stack of pancakes of different diameter. Unfortunately, you cannot eat them unless they are sorted according to their size, with the biggest one at the bottom.

To sort them, you are given a spatula that you can use to split the stack in two parts and then flip

the top part of the stack. Write the pseudo-code of a function sortPancakes that sorts the stack.

The i-th element of array pancakes contains the diameter of the i-th pancake, counting from the bottom. The sortPancakes algorithm can modify the stack only through the spatulaFlip function whose interface is specified below.

(Hint: Notice that you can move a pancake at position x to position y, without modifying the

positions of the order of the other pancakes, using a sequence of spatula flips.)

/* Flips over the stack of pancakes from position pos and returns the result */

            int[] spatulaFlip(int pos, int[] pancakes);

            int[] sortPancakes(int[] pancakes) {

            /*Write your peudo-code here*/

            }

Explanation / Answer

The idea is to do something similar to Selection Sort. Place maximum element at the end one by one and reduce the size of current array by one.
Following are the detailed steps. Let given array be pancakes[] and size of array be n.

Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be curr_size. Do following for every curr_size:

Pseudo code of function sortPancakes that sorts the stack is:

Function name : sortPancakes
Input: Array of diameters of pancakes: pancakes
Output: Sorted array: pancakes

sortPancakes(pancakes)
Begin
n = size of pancakes
For curr_size=n to 2 in pancakes:
maxPancake = findMax(pancakes,curr_size)
if (maxPancake != curr_size-1):
spatulaFlip(maxP,pancakes)
spatulaFlip(curr_size-1,pancakes)
End of if
End of loop
return pancakes
End

----------------------------------------------------------------------------------------------------------------------------------------------------------

findMax(int[] arr, int n) -> returns index of the maximum element in arr[0..n-1]
findMax(int[] arr, int n)
{
for (int mi = 0, i = 0; i < n; ++i)
   if (arr[i] > arr[mi])
     mi = i;
   return mi;
}

----------------------------------------------------------------------------------------------------------------------------------------------------------

spatulaFlip(int pos, int[] pancakes) is already defined in the question which reverses the array pancakes[0...pos].

----------------------------------------------------------------------------------------------------------------------------------------------------------

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.