TheAlgorithms-Python

1
"""
2
Code contributed by Honey Sharma
3
Source: https://en.wikipedia.org/wiki/Cycle_sort
4
"""
5

6

7
def cycle_sort(array: list) -> list:
8
    """
9
    >>> cycle_sort([4, 3, 2, 1])
10
    [1, 2, 3, 4]
11

12
    >>> cycle_sort([-4, 20, 0, -50, 100, -1])
13
    [-50, -4, -1, 0, 20, 100]
14

15
    >>> cycle_sort([-.1, -.2, 1.3, -.8])
16
    [-0.8, -0.2, -0.1, 1.3]
17

18
    >>> cycle_sort([])
19
    []
20
    """
21
    array_len = len(array)
22
    for cycle_start in range(array_len - 1):
23
        item = array[cycle_start]
24

25
        pos = cycle_start
26
        for i in range(cycle_start + 1, array_len):
27
            if array[i] < item:
28
                pos += 1
29

30
        if pos == cycle_start:
31
            continue
32

33
        while item == array[pos]:
34
            pos += 1
35

36
        array[pos], item = item, array[pos]
37
        while pos != cycle_start:
38
            pos = cycle_start
39
            for i in range(cycle_start + 1, array_len):
40
                if array[i] < item:
41
                    pos += 1
42

43
            while item == array[pos]:
44
                pos += 1
45

46
            array[pos], item = item, array[pos]
47

48
    return array
49

50

51
if __name__ == "__main__":
52
    assert cycle_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
53
    assert cycle_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]
54