sorts.reversort

Reversort is a sorting algorithm described in Google Code Jam 2021 Qualification Round.

Algorithm: 1. For i from 1 to N-1:

1. Find the position j of the minimum element in the subarray from position i to N

2. Reverse the subarray from position i to j

Time Complexity: O(n²) - For each position, we find the minimum and reverse Space Complexity: O(n) - Due to list slicing in Python

(can be O(1) with in-place reversal)

For doctests run following command: python3 -m doctest -v reversort.py

For manual testing run: python reversort.py

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

reversort(→ list[T])	Sort a list using the Reversort algorithm.
reversort_cost(→ int)	Calculate the cost of sorting using Reversort.

Module Contents

class sorts.reversort.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.reversort.reversort[T: Comparable](collection: list[T]) → list[T]

Sort a list using the Reversort algorithm.

Reversort works by repeatedly finding the minimum element in the unsorted portion and reversing the subarray from the current position to where the minimum element is located.

Parameters:

collection – A mutable ordered collection with comparable items

Returns:

The sorted collection in ascending order

Examples: >>> reversort([4, 2, 1, 3]) [1, 2, 3, 4] >>> reversort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> reversort([]) [] >>> reversort([-2, -5, -45]) [-45, -5, -2] >>> reversort([1]) [1] >>> reversort([5, 4, 3, 2, 1]) [1, 2, 3, 4, 5] >>> reversort([2, 1, 4, 3]) [1, 2, 3, 4] >>> reversort([-23, 0, 6, -4, 34]) [-23, -4, 0, 6, 34] >>> reversort([1, 2, 3, 4]) [1, 2, 3, 4] >>> reversort([3, 3, 3, 3]) [3, 3, 3, 3] >>> reversort([56]) [56] >>> reversort([0, 5, 2, 3, 2]) == sorted([0, 5, 2, 3, 2]) True >>> reversort([]) == sorted([]) True >>> reversort([-2, -45, -5]) == sorted([-2, -45, -5]) True >>> reversort([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34]) True >>> reversort([‘d’, ‘a’, ‘b’, ‘e’]) == sorted([‘d’, ‘a’, ‘b’, ‘e’]) True >>> reversort([‘z’, ‘a’, ‘y’, ‘b’, ‘x’, ‘c’]) [‘a’, ‘b’, ‘c’, ‘x’, ‘y’, ‘z’] >>> reversort([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6]) [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7] >>> reversort([1, 3.3, 5, 7.7, 2, 4.4, 6]) [1, 2, 3.3, 4.4, 5, 6, 7.7] >>> import random >>> collection_arg = random.sample(range(-50, 50), 100) >>> reversort(collection_arg) == sorted(collection_arg) True >>> import string >>> collection_arg = random.choices(string.ascii_letters + string.digits, k=100) >>> reversort(collection_arg) == sorted(collection_arg) True >>> reversort([1, “a”]) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last):

…

TypeError: ‘<’ not supported between instances of ‘str’ and ‘int’

sorts.reversort.reversort_cost[T: Comparable](collection: list[T]) → int

Calculate the cost of sorting using Reversort.

The cost is defined as the sum of the lengths of all reversed segments. This is based on the Google Code Jam 2021 problem.

Parameters:

collection – A mutable ordered collection with comparable items

Returns:

The total cost of sorting

Examples: >>> reversort_cost([4, 2, 1, 3]) 6 >>> reversort_cost([1, 2]) 1 >>> reversort_cost([7, 6, 5, 4, 3, 2, 1]) 12 >>> reversort_cost([1, 2, 3, 4]) 3 >>> reversort_cost([1]) 0 >>> reversort_cost([]) 0 >>> reversort_cost([1, “a”]) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last):

…

TypeError: ‘<’ not supported between instances of ‘str’ and ‘int’

sorts.reversort.user_input