To the chase

969. Pancake ordering

Given an integer array arr, sort the array using pancake flipping **.

The execution of a pancake flip is as follows:

  • Pick an integerk ，1 <= k <= arr.length
  • Antirotor arrayarr[0...k-1](The subscripts start at 0)

For example, arr = [3,2,1,4], select k = 3 for a pancake flip, invert the rotor array [3,2,1], and get arr = [1,2,3,4].

Returns, as an array, the sequence of k values for pancake flipping operations that order arR. Any valid answer that sorts the array with a number of flips in the 10 * arr.length range will be judged correct.

Resolution:

What is pancake sort

Let’s start with the definition of pancake sort: pie sort is colloquial for quantity problems, sorting unordered stacks of pancakes in order of size when a scraper can be inserted at any point in the stack and used to flip all the pancakes above it. The pancake count is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. It is a variant of the sorting problem, where the only allowed operation is to reverse the elements of certain prefixes of the sequence. Unlike traditional sorting algorithms, which try to sort with as few comparisons as possible, the goal is to sort as few sequences as possible. A variant of this problem involves burnt pancakes, where each pancake has a burnt side, and all pancakes must have another burnt side on the bottom. — From Baidu

And frankly we don’t have to think about how it’s defined, just how does it work, how does it work?

A picture gives you an idea:

As can be seen from the figure, “flipping a pancake” is to reverse the order of the elements within a specified range. After many iterations, you can achieve the purpose of sorting.

What are the rules for ordering pancakes

Understanding the principle of pancake sorting is also the basis for us to achieve pancake sorting. You can see that when we flip the pancake once, we put an element on top, and when we flip it again, we flip it to the specified position. In the picture above, I want to flip 9 to the second-to-last position, so I flip 9 to the top, and then FLIP it to the second-to-last position, so 9 is the second-to-last position. So, we can see that any element can be flipped twice to get where you want it to be, which is the underlying logic of pancake sorting.

Implement pancake sorting

According to the above principle, we need to first find the element to sort, and then determine where it should be sorted, so that we can do two flips of this element.

Find the element to sort

The first element to sort is the largest element, the second element to sort is the second largest element… And so on. In the code, we can read that we’re looking for the NTH largest element, where n is the number of elements already sorted + 1. For example, if we are looking for the third element, we can also understand that 2 elements (2+1) have been arranged.

Set the number of arranged elements to let Ready = 0, then we simply do read ++ after two flips

The implementation finds the ready + 1 largest element:

let getMaxIndex = function (arr, ready) {
    let maxIndex = 0
    for (let index = 1 ; index < arr.length - ready; index++) {
        maxIndex = arr[maxIndex] >  arr[index] ? maxIndex : index
    }
    return maxIndex
}
Copy the code

Perform two flips

Through the double pointer method to achieve the array reversal, the specific principle can refer to the previous article: reverse the array

Flipping method:

let trans = function (arr, index) {
    let left = 0
    let right = index
    while(left < right) {
        arr[left] = arr[left] ^ arr[right]
        arr[right] = arr[left] ^ arr[right]
        arr[left] = arr[left] ^ arr[right]
        left++
        right--
    }
    return arr
}
Copy the code

Implement two flips:

 const maxIndex = getMaxIndex(arr, ready)
arr = trans(arr,maxIndex)
arr = trans(arr, arr.length - 1 - ready)
Copy the code

Final code:

/**
 * @param {number[]} arr
 * @return {number[]}
 */

let getMaxIndex = function (arr, ready) {
    let maxIndex = 0
    for (let index = 1 ; index < arr.length - ready; index++) {
        maxIndex = arr[maxIndex] >  arr[index] ? maxIndex : index
    }
    return maxIndex
}

let trans = function (arr, index) {
    let left = 0
    let right = index
    while(left < right) {
        arr[left] = arr[left] ^ arr[right]
        arr[right] = arr[left] ^ arr[right]
        arr[left] = arr[left] ^ arr[right]
        left++
        right--
    }
    return arr
}

var pancakeSort = function(arr) {
    let ready = 0
    let res = []
    while(ready < arr.length - 1) {
        const maxIndex = getMaxIndex(arr, ready)
        arr = trans(arr,maxIndex)
        arr = trans(arr, arr.length - 1 - ready)
        maxIndex > 0 ? res.push(maxIndex + 1) : ''
        arr.length - 1 - ready > 0 ? res.push(arr.length - 1 - ready + 1) : ''
        ready++
    }
    return res
};
Copy the code

There is one point that can be optimized:

maxIndex > 0 ? res.push(maxIndex + 1) : ''

arr.length - 1 - ready > 0 ? res.push(arr.length - 1 - ready + 1) : ''
Copy the code

So when index is equal to 0, you don’t have to do a flip.