sorts.cyclic_sort

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

Attributes

user_input

Functions

cyclic_sort(→ list[int])

Sorts the input list of n integers from 1 to n in-place

Module Contents

sorts.cyclic_sort.cyclic_sort(nums: list[int]) → list[int]

Sorts the input list of n integers from 1 to n in-place using the Cyclic Sort algorithm.

Parameters:

nums – List of n integers from 1 to n to be sorted.

Returns:

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]

>>> cyclic_sort([1, 2, 2])
Traceback (most recent call last):
...
ValueError: All numbers must be unique, got 2

>>> cyclic_sort([1, 5])
Traceback (most recent call last):
...
ValueError: All numbers must be in range 1 to 2, got 5

sorts.cyclic_sort.user_input