pancake sorting using python

Question

pancake sorting is implemented below. Algorithm is below:

Find the largest out of order pancake and flip it to the bottom (you may need to flip it to the top of the stack first).Repeat step one until the stack is ordered.

from random import randint
def pancake_sort(cakes):
 if not cakes or len(cakes) == 1:
 return cakes
 cake_index = 0
 while cake_index < len(cakes)-1:
 prev_cake_size, current_cake_size = cakes[cake_index], cakes[cake_index+1]
 if prev_cake_size > current_cake_size:
 '''move the highest element to the beginning by reversing
 the cakes from 0 to highest element(including) and then move
 the highest element to the end by reversing the subarray'''
 cakes[0:cake_index+2] = (cakes[0:cake_index+1][::-1] + [cakes[cake_index+1]])[::-1]
 cake_index = 0
 continue
 cake_index += 1
 return cakes
for i in range(randint(0, 5)):
 data = [randint(0, 100) for _ in range(randint(0, 40))]
 if pancake_sort(data[:]) != sorted(data[:]):
 print("failed for", data[:])

• 301_Moved_Permanently: So cakes[0] is the top and cakes[-1] is the bottom, right?

Answer 1

Naming

The name cake_index is very long and makes things hard to read - maybe i would be enough without making things confusing.

The names prev_cake_size and current_cake_size are very misleading are we are not really handling sizes.

More generally, I think we could use more generic terms. My preference is to use the following names:

• cakes becomes lst
• prev_cake_size and current_cake_size become prev_elt and curr_elt
• cake_index becomes i

Style

A few things are unusual in your code regarding style. I suggest reading PEP 8, the style guide for Python code.

Among the things I'd change:

• use the # comment syntax for comments (instead of literal strings)
• use 4-space indentation

Also, it may be clearer to replace your continue by a simple else to make the 2 different situations more explicit.

Useless code

The special case for small lists (size equal to 0 or 1 is not required).

Flipping pancake

The code used to flip pancakes is very complicated and does not really show the kind of operation we perform on your pancake stack. I'd rewrite this:

 lst[:i+1] = reversed(lst[:i+1])
 lst[:i+2] = reversed(lst[:i+2])

Then, the code would look like:

def pancake_sort(lst):
 leng = len(lst)
 i = 0
 while i < leng-1:
 prev_elt, curr_elt = lst[i], lst[i+1]
 if prev_elt > curr_elt:
 # move the highest element to the beginning by reversing
 # the list from 0 to highest element(including) and then move
 # the highest element to the end by reversing the subarray
 lst[:i+1] = reversed(lst[:i+1])
 lst[:i+2] = reversed(lst[:i+2])
 i = 0
 else:
 i += 1
 return lst

Tests

Your tests are complicated because of the amound of calls to random, in particular testing a random number of times.

I'd also suggest using a real testing framework.

It would be a nice youch to also test explicitly edge cases : empty list, list with one element, list with the same elements multiple times.

Finally, instead of calling randint multiple times, you could use random.shuffle(range(50)).

• 301_Moved_Permanently: I won't make an other answer as I basically wanted to say pretty much the same thing, except I’d use upper_bound = len(lst) - 1 instead of leng. Also would you say it's a good thing to replace the two reversed by lst[1:i+2] = lst[:i+1]; lst[0] = curr_elt which is equivalent in result and faster but which sacrifice the "pancake" part of flipping stuff in the list?
• SylvainD: @MathiasEttinger your upper_bound idea seems better than what I've done. As for the flipping, I do prefer to make things explicit (as we're not working on the best sorting algorithm anyway).