Pancake sort: Given an unsorted array, sort the given array using only a `flip` operation


  • 0
    Y

    Given an unsorted array, sort the given array using only a flip operation:

    flip(arr, i): Reverse array from 0 to i

    This is given to you:

    def flip(arr, i):
        # Implemented only for testing
        l, r = 0, i
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1
    

    My code:

    def pancakeSort(arr):
        for i in range(len(arr)-1, -1, -1):
            best_index = findMaxUpTo(arr, i)
            flip(arr, best_index)
            flip(arr, i)
        return arr
    
    
    def findMaxUpTo(arr, rightBound):
        best_index = 0
        max_val = None
        for i in range(rightBound + 1):
            if arr[i] > max_val:
                best_index = i
                max_val = arr[i]
        return best_index
    

    Test:

    if __name__ == '__main__':
        nums = [-3, 2, 23, 5, 8, 2, 9, 0, 0, -2, -4]
        print pancakeSort(nums)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.