Sorting Pancakes

Pramp Pancake Sort Problem

Given an array of integers arr:

1. Write a function flip(arr, k) that reverses the order of the first kelements in the array arr.
2. Write a function pancakeSort(arr) that sorts and returns the input array. You are allowed to use only the function flip you wrote in the first step in order to make changes in the array.

Example:

input:  arr = [1, 5, 4, 3, 2]

output: [1, 2, 3, 4, 5] # to clarify, this is pancakeSort's output

Analyze the time and space complexities of your solution.

Note: it’s called pancake sort because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes in the plate. To read more about the problem, see the Pancake Sorting Wikipedia page.

Constraints:

• [time limit] 5000ms
• [input] array.integer arr
• [input] integer k
  • 0 ≤ k
• [output] array.integer

Solution

func flip(_ arr: [Int], _ k: Int) -> [Int] {
    return arr[0...k].reversed() + arr[k+1.. [Int] {
    var arr = arr
    var partition = arr.count - 1
    var maxValue = 0
    var maxIndex = 0
    while partition > 0 {
        for (i, val) in arr[0...partition].enumerated() {
            if val >= maxValue {
                maxValue = val
                maxIndex = i
            }
        }
        arr = flip(arr, maxIndex)
        arr = flip(arr, partition)
        partition -= 1
        maxValue = 0
        maxIndex = 0
    }
    
    return arr
}

Time and Space Complexity

Time complexity is \(O(n^2) \). This is a comparison sorting algorithm. We utilize a double loop. The outer loop iterates through every element. The inner loop decreases in size by 1 on each iteration of the outer loop.

The space complexity is \(O(n) \). We never utilize more space than the size of the original input array.

Think Different

1. Forgot to reset my values back to 0 before looping through again.
2. Partition while loop incorrectly set to while partition > 1.