Python/sorts/cyclic_sort.py at master · ivan53/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
This is a pure Python implementation of the Cyclic Sort algorithm.

For doctests run following command:
python -m doctest -v cyclic_sort.py
or
python3 -m doctest -v cyclic_sort.py
For manual testing run:
python cyclic_sort.py
or
python3 cyclic_sort.py
"""


defcyclic_sort(nums: list[int]) ->list[int]:
"""
 Sorts the input list of n integers from 1 to n in-place
 using the Cyclic Sort algorithm.

 :param nums: List of n integers from 1 to n to be sorted.
 :return: The same list sorted in ascending order.

 Time complexity: O(n), where n is the number of integers in the list.

 Examples:
 >>> cyclic_sort([])
 []
 >>> cyclic_sort([3, 5, 2, 1, 4])
 [1, 2, 3, 4, 5]
 """

# Perform cyclic sort
index=0
whileindex<len(nums):
# Calculate the correct index for the current element
correct_index=nums[index] -1
# If the current element is not at its correct position,
# swap it with the element at its correct index
ifindex!=correct_index:
nums[index], nums[correct_index] =nums[correct_index], nums[index]
else:
# If the current element is already in its correct position,
# move to the next element
index+=1

returnnums


if__name__=="__main__":
importdoctest

doctest.testmod()
user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(*cyclic_sort(unsorted), sep=",")