mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
RokeshwaranandChristian Clauss
9ec2f097fe
* sorts: make recursive_insertion_sort generic over Comparable items Part of #15234 - switch rec_insertion_sort/insert_next to the Comparable/TypeVar-bound MutableSequence[T] pattern (in-place sorts bucket) per the convention discussed on #15234 - make rec_insertion_sort return the sorted collection and give n a default of len(collection), so it can be called with a single argument like the other sorts in the shared test battery - add a string doctest - register rec_insertion_sort in tests/test_sorts.py's shared SORTS battery and the non-comparable-items rejection test * fix: keep rec_insertion_sort in-place with None return, per maintainer review - Revert n to a required parameter and drop the MutableSequence[T] return value; rec_insertion_sort stays a pure in-place sort returning None, as requested in review. - Keep the Comparable/TypeVar generalization (no PEP 695 syntax, to match the existing TypeVar style in the file). - Keep the non-int (string) doctest. - tests/test_sorts.py: rec_insertion_sort no longer fits the shared SORTS battery (which asserts on a returned value), so it's removed from that tuple and given its own parametrized in-place test, plus its own non-comparable-items rejection test. * test: adjust test_sorts.py for rec_insertion_sort's None-returning in-place contract rec_insertion_sort no longer fits the shared SORTS battery (which asserts on a returned value), so it's removed from that tuple and given its own parametrized in-place test (checked against sorted()) plus its own non-comparable-items rejection test. * Apply batched suggestions from code review Co-authored-by: Christian Clauss <cclauss@me.com> --------- Co-authored-by: Christian Clauss <cclauss@me.com>
91 lines
2.1 KiB
Python
91 lines
2.1 KiB
Python
"""
|
|
A recursive implementation of the insertion sort algorithm
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
from collections.abc import MutableSequence
|
|
from typing import Any, Protocol, TypeVar
|
|
|
|
|
|
class Comparable(Protocol):
|
|
def __lt__(self, other: Any, /) -> bool: ...
|
|
|
|
|
|
T = TypeVar("T", bound=Comparable)
|
|
|
|
|
|
def rec_insertion_sort[T](collection: MutableSequence[T], n: int) -> None:
|
|
"""
|
|
Given a collection of comparable elements and its length, sorts the
|
|
collection in place in ascending order.
|
|
|
|
:param collection: A mutable collection of comparable elements
|
|
:param n: The length of collection
|
|
|
|
>>> col = [1, 2, 1]
|
|
>>> rec_insertion_sort(col, len(col))
|
|
>>> col
|
|
[1, 1, 2]
|
|
|
|
>>> col = [2, 1, 0, -1, -2]
|
|
>>> rec_insertion_sort(col, len(col))
|
|
>>> col
|
|
[-2, -1, 0, 1, 2]
|
|
|
|
>>> col = [1]
|
|
>>> rec_insertion_sort(col, len(col))
|
|
>>> col
|
|
[1]
|
|
|
|
>>> col = ['d', 'a', 'b', 'e', 'c']
|
|
>>> rec_insertion_sort(col, len(col))
|
|
>>> col
|
|
['a', 'b', 'c', 'd', 'e']
|
|
"""
|
|
# Checks if the entire collection has been sorted
|
|
if len(collection) <= 1 or n <= 1:
|
|
return
|
|
|
|
insert_next(collection, n - 1)
|
|
rec_insertion_sort(collection, n - 1)
|
|
|
|
|
|
def insert_next[T](collection: MutableSequence[T], index: int) -> None:
|
|
"""
|
|
Inserts the '(index-1)th' element into place
|
|
|
|
>>> col = [3, 2, 4, 2]
|
|
>>> insert_next(col, 1)
|
|
>>> col
|
|
[2, 3, 4, 2]
|
|
|
|
>>> col = [3, 2, 3]
|
|
>>> insert_next(col, 2)
|
|
>>> col
|
|
[3, 2, 3]
|
|
|
|
>>> col = []
|
|
>>> insert_next(col, 1)
|
|
>>> col
|
|
[]
|
|
"""
|
|
# Checks order between adjacent elements
|
|
if index >= len(collection) or collection[index - 1] <= collection[index]:
|
|
return
|
|
|
|
# Swaps adjacent elements since they are not in ascending order
|
|
collection[index - 1], collection[index] = (
|
|
collection[index],
|
|
collection[index - 1],
|
|
)
|
|
|
|
insert_next(collection, index + 1)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
numbers = input("Enter integers separated by spaces: ")
|
|
number_list: list[int] = [int(num) for num in numbers.split()]
|
|
rec_insertion_sort(number_list, len(number_list))
|
|
print(number_list)
|