pancake sort Algorithm
A variant of the problem is pertained with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.
In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen) pertained the burnt pancake problem. The pancake sorting problem was first posed by Jacob E. Goodman, write under the pseudonym" Harry Dweighter" (" harried waiter").Although seen more often as an educational device, pancake sorting also looks in applications in parallel CPU networks, in which it can supply an effective routing algorithm between CPUs. Whereas efficient exact algorithms have been found for the signed sorting by reversals, the problem of sorting by reversals has been proven to be hard even to estimate to within certain constant factor, and also proven to be approximable in polynomial time to within the estimation factor 1.375.
"""
This is a pure Python implementation of the pancake sort algorithm
For doctests run following command:
python3 -m doctest -v pancake_sort.py
or
python -m doctest -v pancake_sort.py
For manual testing run:
python pancake_sort.py
"""
def pancake_sort(arr):
"""Sort Array with Pancake Sort.
:param arr: Collection containing comparable items
:return: Collection ordered in ascending order of items
Examples:
>>> pancake_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> pancake_sort([])
[]
>>> pancake_sort([-2, -5, -45])
[-45, -5, -2]
"""
cur = len(arr)
while cur > 1:
# Find the maximum number in arr
mi = arr.index(max(arr[0:cur]))
# Reverse from 0 to mi
arr = arr[mi::-1] + arr[mi + 1 : len(arr)]
# Reverse whole list
arr = arr[cur - 1 :: -1] + arr[cur : len(arr)]
cur -= 1
return arr
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(pancake_sort(unsorted))
