"""
Code contributed by Honey Sharma
Source: https://en.wikipedia.org/wiki/Cycle_sort
"""


def cycle_sort(array: list) -> list:
    """
    >>> cycle_sort([4, 3, 2, 1])
    [1, 2, 3, 4]

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

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

    >>> cycle_sort([])
    []
    """
    array_len = len(array)
    for cycle_start in range(array_len - 1):
        item = array[cycle_start]

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

        if pos == cycle_start:
            continue

        while item == array[pos]:
            pos += 1

        array[pos], item = item, array[pos]
        while pos != cycle_start:
            pos = cycle_start
            for i in range(cycle_start + 1, array_len):
                if array[i] < item:
                    pos += 1

            while item == array[pos]:
                pos += 1

            array[pos], item = item, array[pos]

    return array


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

Problem Statement

Given an unsorted array of n elements, write a function to sort the array

Approach

• If the element is already at its correct position do nothing
• Otherwise, find the correct position of a by counting the total number of elements that are less than current element
• Insert current element into its correct position
• Set replaced element as new current element and find its correct position
• Continue process until array is sorted

Time Complexity

O(n^2) Worst case performance

O(n^2) Best-case performance

O(n^2) Average performance

Space Complexity

O(n) Worst case

Application of algorithm

• Cycle sort algorithm is useful for situations where memory write or element swap operations are costly.

Example

A single cycle of sorting array | b | d | e | a | c |

1. Select element for which the cycle is run, i.e. "b".

|b|d|e|a|c|

b - current element 

2. Find correct location for current element and update current element.

|b|b|e|a|c|

d - current element 

3. One more time, find correct location for current element and update current element.

|b|b|e|d|c|

a - current element 

4. Current element is inserted into position of initial element "b" which ends the cycle.

|a|b|e|d|c|

a - current element 

5. New cycle should be started for next element.

Video Explanation

A video explaining the Cycle Sort Algorithm

The Algorithms Page

Cycle Sort