Cycle Sort in Python3

Below is an example of the Cycle Sort algorithm in Python3. See the Cycle Sort page for more information and implementations.


cycle-sort in Python3

def cycle_sort(array):
    # loop from the beginning of the array to the second to last item
    for currentIndex in range(0, len(array) - 1):
        # save the value of the item at the currentIndex
        item = array[currentIndex];

        currentIndexCopy = currentIndex;
        # loop through all indexes that proceed the currentIndex
        for i in range(currentIndex + 1, len(array)):
            if array[i] < item: currentIndexCopy += 1
            i += 1

        # if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy
        if currentIndexCopy == currentIndex:
            currentIndex += 1
            continue

        # skip duplicates
        while item == array[currentIndexCopy]: currentIndexCopy += 1

        # swap
        temp = array[currentIndexCopy]
        array[currentIndexCopy] = item
        item = temp

        # repeat above steps as long as we can find values to swap
        while currentIndexCopy != currentIndex:

            currentIndexCopy = currentIndex
            # loop through all indexes that proceed the currentIndex
            i = currentIndex + 1
            while i < len(array):
                if array[i] < item: currentIndexCopy += 1
                i += 1

            # skip duplicates
            while item == array[currentIndexCopy]: currentIndexCopy += 1

            # swap
            temp = array[currentIndexCopy]
            array[currentIndexCopy] = item
            item = temp

        currentIndex += 1

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    cycle_sort(array)
    print(array)

Discussion