TheAlgorithms-Python

1
"""
2
A recursive implementation of the insertion sort algorithm
3
"""
4

5
from __future__ import annotations
6

7

8
def rec_insertion_sort(collection: list, n: int):
9
    """
10
    Given a collection of numbers and its length, sorts the collections
11
    in ascending order
12

13
    :param collection: A mutable collection of comparable elements
14
    :param n: The length of collections
15

16
    >>> col = [1, 2, 1]
17
    >>> rec_insertion_sort(col, len(col))
18
    >>> col
19
    [1, 1, 2]
20

21
    >>> col = [2, 1, 0, -1, -2]
22
    >>> rec_insertion_sort(col, len(col))
23
    >>> col
24
    [-2, -1, 0, 1, 2]
25

26
    >>> col = [1]
27
    >>> rec_insertion_sort(col, len(col))
28
    >>> col
29
    [1]
30
    """
31
    # Checks if the entire collection has been sorted
32
    if len(collection) <= 1 or n <= 1:
33
        return
34

35
    insert_next(collection, n - 1)
36
    rec_insertion_sort(collection, n - 1)
37

38

39
def insert_next(collection: list, index: int):
40
    """
41
    Inserts the '(index-1)th' element into place
42

43
    >>> col = [3, 2, 4, 2]
44
    >>> insert_next(col, 1)
45
    >>> col
46
    [2, 3, 4, 2]
47

48
    >>> col = [3, 2, 3]
49
    >>> insert_next(col, 2)
50
    >>> col
51
    [3, 2, 3]
52

53
    >>> col = []
54
    >>> insert_next(col, 1)
55
    >>> col
56
    []
57
    """
58
    # Checks order between adjacent elements
59
    if index >= len(collection) or collection[index - 1] <= collection[index]:
60
        return
61

62
    # Swaps adjacent elements since they are not in ascending order
63
    collection[index - 1], collection[index] = (
64
        collection[index],
65
        collection[index - 1],
66
    )
67

68
    insert_next(collection, index + 1)
69

70

71
if __name__ == "__main__":
72
    numbers = input("Enter integers separated by spaces: ")
73
    number_list: list[int] = [int(num) for num in numbers.split()]
74
    rec_insertion_sort(number_list, len(number_list))
75
    print(number_list)
76