mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
e49caf57d0
* types(reverse_selection): constrain items to Comparable Bind reverse_selection_sort's element type to a Comparable Protocol so the signature says "a list of items that can be compared with each other" instead of a bare list, and keep the element type in the return. reverse_subarray only swaps elements and never compares them, so its TypeVar stays unbounded. Also adds doctests for a comparable non-int type (strings, floats) and for the failure mode: mixing non-comparable items must raise TypeError rather than silently mis-sort. The test battery picks the sort up for the shared cases and for the rejection check. * updating DIRECTORY.md --------- Co-authored-by: AuroraAeon <auroraeon@users.noreply.github.com> Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
105 lines
2.6 KiB
Python
105 lines
2.6 KiB
Python
"""
|
|
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))
|