reverse_selection.py

"""
A pure Python implementation of the Reverse Selection Sort algorithm

This algorithm progressively sorts the array by reversing subarrays

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

For manual testing run:
python3 reverse_selection.py
"""

from typing import Any, Protocol


class Comparable(Protocol):
    def __lt__(self, other: Any, /) -> bool: ...


def reverse_subarray[T](arr: list[T], start: int, end: int) -> None:
    """
    Reverse a subarray in-place.

    :param arr: the array containing the subarray to be reversed
    :param start: the starting index of the subarray
    :param end: the ending index of the subarray

    Examples:
    >>> lst = [1, 2, 3, 4, 5]
    >>> reverse_subarray(lst, 1, 3)
    >>> lst
    [1, 4, 3, 2, 5]

    >>> lst = [1]
    >>> reverse_subarray(lst, 0, 0)
    >>> lst
    [1]

    >>> lst = [1, 2]
    >>> reverse_subarray(lst, 0, 1)
    >>> lst
    [2, 1]
    """
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1


def reverse_selection_sort[T: Comparable](collection: list[T]) -> list[T]:
    """
    A pure implementation of reverse selection sort algorithm in Python

    :param collection: some mutable ordered collection with heterogeneous
    comparable items inside
    :return: the same collection sorted in ascending order

    Examples:
    >>> reverse_selection_sort([1, 9, 5, 21, 17, 6])
    [1, 5, 6, 9, 17, 21]

    >>> reverse_selection_sort([])
    []

    >>> reverse_selection_sort([-3, -17, -48])
    [-48, -17, -3]

    >>> reverse_selection_sort([1, 1, 1, 1])
    [1, 1, 1, 1]

    >>> reverse_selection_sort([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]

    >>> reverse_selection_sort(["banana", "apple", "cherry"])
    ['apple', 'banana', 'cherry']

    >>> reverse_selection_sort([3.14, 1.5, 2.7])
    [1.5, 2.7, 3.14]

    >>> reverse_selection_sort([1, "a"])  # doctest: +ELLIPSIS
    Traceback (most recent call last):
    ...
    TypeError: ...
    """
    n = len(collection)
    for i in range(n - 1):
        # Find the minimum element in the unsorted portion
        min_idx = i
        for j in range(i + 1, n):
            if collection[j] < collection[min_idx]:
                min_idx = j

        # If the minimum is not at the start of the unsorted portion,
        # reverse the subarray to bring it to the front
        if min_idx != i:
            reverse_subarray(collection, i, min_idx)

    return collection


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(reverse_selection_sort(unsorted))