sorts.pancake_sort

Pancake Sort Algorithm Implementation.

A pure Python implementation of the Pancake Sort algorithm. Pancake sort is a sorting algorithm that sorts an array by repeatedly flipping subsections of the array, similar to how you might sort a stack of pancakes by inserting a spatula and flipping the top portion.

The algorithm works by finding the maximum element, flipping it to the top, then flipping it down to its correct position. This process is repeated for the remaining unsorted portion.

Time Complexity: O(n^2) - We perform n iterations, each with up to 2 flips Space Complexity: O(1) - In-place sorting, only uses a constant amount of extra space

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

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

pancake_sort(→ list[T])

Sort Array with Pancake Sort.

Module Contents

class sorts.pancake_sort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: Any, /) → bool

sorts.pancake_sort.pancake_sort[T: Comparable](arr: collections.abc.Sequence[T]) → list[T]

Sort Array with Pancake Sort.

Parameters:

arr – some ordered collection with heterogeneous comparable items

inside :return: the same collection ordered by ascending

Time Complexity: (O(n^2)) Space Complexity: (O(n))

Examples: >>> pancake_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> pancake_sort([]) [] >>> pancake_sort([-2, -5, -45]) [-45, -5, -2] >>> pancake_sort([‘d’, ‘a’, ‘b’, ‘e’, ‘c’]) == sorted([‘d’, ‘a’, ‘b’, ‘e’, ‘c’]) True >>> import random >>> collection = random.sample(range(-50, 50), 100) >>> pancake_sort(collection) == sorted(collection) True >>> import string >>> collection = random.choices(string.ascii_letters + string.digits, k=100) >>> pancake_sort(collection) == sorted(collection) True

sorts.pancake_sort.user_input