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

Functions

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

Module Contents

sorts.reversort.reversort(collection: list[Any]) → list[Any]

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

sorts.reversort.reversort_cost(collection: list[Any]) → 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

sorts.reversort.user_input