Pancake Sorting

The problem of pancake sorting is unique because it doesn’t allow us to simply swap two elements; instead, we can reverse an entire prefix of the array.

Here’s a general strategy to sort the array using pancake flips:

1. Find the Largest Unsorted Element: Find the largest element that is not in its correct position.

2. Flip to Beginning: Flip the sub-array that ends with the largest unsorted element, so that this element comes to the beginning of the array.

3. Flip to Correct Position: Now that the largest unsorted element is at the beginning of the array, flip the sub-array that ends with the correct position for this element. This places the element in its correct position.

4. Repeat for Remaining Elements: Repeat steps 1-3 for the remaining unsorted elements.

Here’s the code implementing this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        result = []

        # Function to flip the sub-array arr[0...k-1]
        def flip(subarr, k):
            i = 0
            while i < k // 2:
                subarr[i], subarr[k - i - 1] = subarr[k - i - 1], subarr[i]
                i += 1

        for value_to_sort in range(len(arr), 0, -1):
            # Position of the value in the current array
            position = arr.index(value_to_sort)

            # If the value is already in the correct position, continue
            if position == value_to_sort - 1:
                continue

            # Flip to get the value at the beginning
            if position != 0:
                result.append(position + 1)
                flip(arr, position + 1)

            # Flip to get the value to its correct position
            result.append(value_to_sort)
            flip(arr, value_to_sort)

        return result

This code returns the sequence of flips required to sort the given array. The flip function is a simple reversal of the first k elements of the given sub-array. The main part of the algorithm iteratively finds the largest unsorted element, flips it to the beginning, then flips it to its correct final position.