Pancake Sorting

Pancake Sorting

Given an array of integers A, We need to sort the array performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 0 <= k < A.length.
• Reverse the sub-array A[0...k].

For example, if A = [3,2,1,4] and we performed a pancake flip choosing k = 2, we reverse the sub-array [3,2,1], so A = [1,2,3,4] after the pancake flip at k = 2.

Return an array of the k-values of the pancake flips that should be performed in order to sort A. Any valid answer that sorts the array within  10 * A.length  flips will be judged as correct.

 

Example 1:

Input: A = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k = 4): A = [1, 4, 2, 3]
After 2nd flip (k = 2): A = [4, 1, 2, 3]
After 3rd flip (k = 4): A = [3, 2, 1, 4]
After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.

Example 2:

Input: A = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

 

Constraints:

• 1 <= A.length <= 100
• 1 <= A[i] <= A.length
• All integers in A are unique (i.e. A is a permutation of the integers from 1 to A.length).

The idea is simple. First, we move the number to the head of the list, then we can switch it with any other element by performing another pancake flip.

Algorithm

One can inspire from the bubble sort to implement the algorithm.

• First of all, we implement a function called flip(list, k), which performs the pancake flip on the prefix of list[0:k] (in Python).

• The main algorithm runs a loop over the values of the list, starting from the largest one.

  • At each round, we identify the value to sort (named as value_to_sort), which is the number we would put in place at this round.

  • We then locate the index of the value_to_sort.

  • If the value_to_sort is not at its place already, we can then perform at most two pancake flips as we explained in the intuition.

  • At the end of the round, the value_to_sort would be put in place.

C++

 class Solution {

public:

    bool sorted(vector<int> &A)

    {

        for(int i=0;i<A.size()-1;++i)

            if(A[i]>A[i+1])

                return false;

        return true;

    }

    vector<int> pancakeSort(vector<int>& A) { 

        vector<int> ans;

        int j=0;

        if(sorted(A)) return {};

        

        while(j<A.size()-1)

        {

            auto it=max_element(A.begin(),A.end()-j)-A.begin();

             int l=A.size()-it;

            if(it!=0)

            {

            reverse(A.begin(),A.begin()+it+1);

            ans.push_back(it+1);

            }

            reverse(A.begin(),A.end()-j);

            ans.push_back(A.end()-j-A.begin());

             ++j;

        }

        return ans;

    };

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

JAVA

class Solution {

    /**

     * sort like bubble-sort i.e. sink the largest number to the bottom at each round.

     */

    public List<Integer> pancakeSort(int[] A) {

        List<Integer> ans = new ArrayList<>();

        for (int valueToSort = A.length; valueToSort > 0; valueToSort--) {

            // locate the position for the value to sort in this round

            int index = this.find(A, valueToSort);

            // sink the value_to_sort to the bottom,

            // with at most two steps of pancake flipping.

            if (index == valueToSort - 1)

                continue;

            // 1). flip the value to the head if necessary

            if (index != 0) {

                ans.add(index + 1);

                this.flip(A, index + 1);

            }

            // 2). now that the value is at the head, flip it to the bottom

            ans.add(valueToSort);

            this.flip(A, valueToSort);

        }

        return ans;

    }

    protected void flip(int[] sublist, int k) {

        int i = 0;

        while (i < k / 2) {

            int temp = sublist[i];

            sublist[i] = sublist[k - i - 1];

            sublist[k - i - 1] = temp;

            i += 1;

        }

    }

    protected int find(int[] a, int target) {

        for (int i = 0; i < a.length; i++)

            if (a[i] == target)

                return i;

        return -1;

    }

}

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

PYTHON:

class Solution:

    def pancakeSort(self, A: List[int]) -> List[int]:

        """ sort like bubble-sort

            sink the largest number to the bottom at each round

        """

        def flip(sublist, k):

            i = 0

            while i < k / 2:

                sublist[i], sublist[k-i-1] = sublist[k-i-1], sublist[i]

                i += 1

        ans = []

        value_to_sort = len(A)

        while value_to_sort > 0:

            # locate the position for the value to sort in this round

            index = A.index(value_to_sort)

            # sink the value_to_sort to the bottom,

            #   with at most two steps of pancake flipping.

            if index != value_to_sort - 1:

                # flip the value to the head if necessary

                if index != 0:

                    ans.append(index+1)

                    flip(A, index+1)

                # now that the value is at the head, flip it to the bottom

                ans.append(value_to_sort)

                flip(A, value_to_sort)

            # move on to the next round

            value_to_sort -= 1

        return ans