TheAlgorithms-Python

1
"""
2
This is a Python implementation of the circle sort algorithm
3

4
For doctests run following command:
5
python3 -m doctest -v circle_sort.py
6

7
For manual testing run:
8
python3 circle_sort.py
9
"""
10

11

12
def circle_sort(collection: list) -> list:
13
    """A pure Python implementation of circle sort algorithm
14

15
    :param collection: a mutable collection of comparable items in any order
16
    :return: the same collection in ascending order
17

18
    Examples:
19
    >>> circle_sort([0, 5, 3, 2, 2])
20
    [0, 2, 2, 3, 5]
21
    >>> circle_sort([])
22
    []
23
    >>> circle_sort([-2, 5, 0, -45])
24
    [-45, -2, 0, 5]
25
    >>> collections = ([], [0, 5, 3, 2, 2], [-2, 5, 0, -45])
26
    >>> all(sorted(collection) == circle_sort(collection) for collection in collections)
27
    True
28
    """
29

30
    if len(collection) < 2:
31
        return collection
32

33
    def circle_sort_util(collection: list, low: int, high: int) -> bool:
34
        """
35
        >>> arr = [5,4,3,2,1]
36
        >>> circle_sort_util(lst, 0, 2)
37
        True
38
        >>> arr
39
        [3, 4, 5, 2, 1]
40
        """
41

42
        swapped = False
43

44
        if low == high:
45
            return swapped
46

47
        left = low
48
        right = high
49

50
        while left < right:
51
            if collection[left] > collection[right]:
52
                collection[left], collection[right] = (
53
                    collection[right],
54
                    collection[left],
55
                )
56
                swapped = True
57

58
            left += 1
59
            right -= 1
60

61
        if left == right and collection[left] > collection[right + 1]:
62
            collection[left], collection[right + 1] = (
63
                collection[right + 1],
64
                collection[left],
65
            )
66

67
            swapped = True
68

69
        mid = low + int((high - low) / 2)
70
        left_swap = circle_sort_util(collection, low, mid)
71
        right_swap = circle_sort_util(collection, mid + 1, high)
72

73
        return swapped or left_swap or right_swap
74

75
    is_not_sorted = True
76

77
    while is_not_sorted is True:
78
        is_not_sorted = circle_sort_util(collection, 0, len(collection) - 1)
79

80
    return collection
81

82

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