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[:])

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)).