Search

Cycle Sort

Cycle Sort is an unstable comparison sort algorithm with poor performance. Cycle Sort uses the insertion method and performs at O(n2) in the best, average, and worst case.

Table of contents

Performance

Best
Ω(n2)
Average
Θ(n2)
Worst
O(n2)

Code

public class CycleSort {
    public static void main(String[] args)
    {
        int[] array1 = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        int[] array2 = {2, 1, 5, 2, 9, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8};

        CycleSort sorter = new CycleSort();
        sorter.cycleSort(array1);
        sorter.cycleSort(array2);

        System.out.println(java.util.Arrays.toString(array1));
        System.out.println(java.util.Arrays.toString(array2));
    }

    void cycleSort(int[] array)
    {
        // step 1: loop from the beginning of the array to the second to last item
        for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
        {
            // step 2: save the value of the item at the currentIndex
            int item = array[currentIndex];
            // step 3: save a copy of the current index
            int currentIndexCopy = currentIndex;

            // step 4: loop through all indexes that proceed the currentIndex
            for (int i = currentIndex + 1; i < array.length; i++)
                if (array[i] < item)
                    currentIndexCopy++;

            // step 5: if currentIndexCopy has not changed, the item at the currentIndex is already in the correct position
            if (currentIndexCopy == currentIndex)
                continue;

            // step 6: skip duplicates
            while (item == array[currentIndexCopy])
                currentIndexCopy++;

            // step 7: swap
            int temp = array[currentIndexCopy];
            array[currentIndexCopy] = item;
            item = temp;

            // step 8: repeat steps 4, 6 and 7 above as long as we can find values to swap
            while (currentIndexCopy != currentIndex)
            {

                // step 9: save a copy of the currentIndex
                currentIndexCopy = currentIndex;

                // step 10: repeat step 4
                for (int i = currentIndex + 1; i < array.length; i++)
                    if (array[i] < item)
                        currentIndexCopy++;

                // step 10: repeat step 6
                while (item == array[currentIndexCopy])
                    currentIndexCopy++;

                // step 10: repeat step 7
                temp = array[currentIndexCopy];
                array[currentIndexCopy] = item;
                item = temp;
            }
        }
    }
}
class CycleSort<T extends Comparable<? super T>> {

    public static void main(String[] args)
    {
        String[] array = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        CycleSort<String> sorter = new CycleSort<>();
        sorter.cycleSort(array);
        System.out.println(java.util.Arrays.toString(array));
    }

    void cycleSort(T[] array)
    {
        // loop from the beginning of the array to the second to last item
        for (int currentIndex = 0; currentIndex < array.length - 1; currentIndex++)
        {
            // save the value of the item at the currentIndex
            T   item             = array[currentIndex];
            int currentIndexCopy = currentIndex;

            // loop through all indexes that proceed the currentIndex
            for (int i = currentIndex + 1; i < array.length; i++)
                if (array[i].compareTo(item) < 0)
                    currentIndexCopy++;

            // if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy
            if (currentIndexCopy == currentIndex)
                continue;

            // skip duplicates
            while (item == array[currentIndexCopy])
                currentIndexCopy++;

            // swap
            T 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
                for (int i = currentIndex + 1; i < array.length; i++)
                    if (array[i].compareTo(item) < 0)
                        currentIndexCopy++;

                // skip duplicates
                while (item == array[currentIndexCopy])
                    currentIndexCopy++;

                // swap
                temp = array[currentIndexCopy];
                array[currentIndexCopy] = item;
                item = temp;
            }
        }
    }
}
#include <iostream>
#include <vector>

void cycleSort(std::vector<int> &arr) {
    // step 1: loop from the beginning of the arr to the second to last item
    for (int currentIndex = 0; currentIndex < arr.size() - 1; currentIndex++) {
        // step 2: save the value of the item at the currentIndex
        int item = arr[currentIndex];
        // step 3: save a copy of the current index
        int currentIndexCopy = currentIndex;

        // step 4: loop through all indexes that proceed the currentIndex
        for (int i = currentIndex + 1; i < arr.size(); i++)
            if (arr[i] < item)
                currentIndexCopy++;

        // step 5: if currentIndexCopy has not changed, the item at the currentIndex is already in the correct position
        if (currentIndexCopy == currentIndex)
            continue;

        // step 6: skip duplicates
        while (item == arr[currentIndexCopy])
            currentIndexCopy++;

        // step 7: swap
        int temp = arr[currentIndexCopy];
        arr[currentIndexCopy] = item;
        item = temp;

        // step 8: repeat steps 4, 6 and 7 above as long as we can find values to swap
        while (currentIndexCopy != currentIndex) {

            // step 9: save a copy of the currentIndex
            currentIndexCopy = currentIndex;

            // step 10: repeat step 4
            for (int i = currentIndex + 1; i < arr.size(); i++)
                if (arr[i] < item)
                    currentIndexCopy++;

            // step 10: repeat step 6
            while (item == arr[currentIndexCopy])
                currentIndexCopy++;

            // step 10: repeat step 7
            temp = arr[currentIndexCopy];
            arr[currentIndexCopy] = item;
            item = temp;
        }
    }
}


int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    cycleSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func cycleSort(array: inout [Int]) {
    // step 1: loop from the beginning of the array to the second to last item
    for currentIndex in 0..<(array.count - 1) {
        // step 2: save the value of the item at the currentIndex
        var item = array[currentIndex]
        // step 3: save a copy of the current index
        var currentIndexCopy = currentIndex

        // step 4: loop through all indexes that proceed the currentIndex
        for i in currentIndex + 1..<array.count {
            if (array[i] < item) {
                currentIndexCopy += 1
            }
        }

        // step 5: if currentIndexCopy has not changed, the item at the currentIndex is already in the correct position
        if (currentIndexCopy == currentIndex) {
            continue;
        }

        // step 6: skip duplicates
        while (item == array[currentIndexCopy]) {
            currentIndexCopy += 1
        }

        // step 7: swap
        var temp = array[currentIndexCopy]
        array[currentIndexCopy] = item
        item = temp

        // step 8: repeat steps 4, 6 and 7 above as long as we can find values to swap
        while (currentIndexCopy != currentIndex) {

            // step 9: save a copy of the currentIndex
            currentIndexCopy = currentIndex

            // step 10: repeat step 4
            for i in (currentIndex + 1)..<array.count {
                if array[i] < item {
                    currentIndexCopy += 1
                }
            }

            // step 10: repeat step 6
            while (item == array[currentIndexCopy]) {
                currentIndexCopy += 1
            }

            // step 10: repeat step 7
            temp = array[currentIndexCopy]
            array[currentIndexCopy] = item
            item = temp
        }
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
cycleSort(array: &array)
print(array)
function cycleSort(array) {
  // loop from the beginning of the array to the second to last item
  for (let currentIndex = 0; currentIndex < array.length - 1; currentIndex++) {
    // save the value of the item at the currentIndex
    let item = array[currentIndex]

    let currentIndexCopy = currentIndex
    // loop through all indexes that proceed the currentIndex
    for (let i = currentIndex + 1; i < array.length; i++)
      if (array[i] < item)
        currentIndexCopy++

    // if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy
    if (currentIndexCopy == currentIndex)
      continue

    // skip duplicates
    while (item == array[currentIndexCopy])
      currentIndexCopy++

    // swap
    let 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
      for (let i = currentIndex + 1; i < array.length; i++)
        if (array[i] < item)
          currentIndexCopy++

      // skip duplicates
      while (item == array[currentIndexCopy])
        currentIndexCopy++

      // swap
      temp = array[currentIndexCopy]
      array[currentIndexCopy] = item
      item = temp
    }
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
cycleSort(array)
alert(array)
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)

Walkthrough

The algorithm executes in the following steps:

  1. Create a loop that begins at the beginning of the array and ends at the second to last item in the array
  2. Save the value of the item at the current index.
    In our example, we named our value item.
  3. Make a copy of the current index.
    In our example, we named our index copy currentIndexCopy.
  4. Create an additional loop that begins at one index after the currentIndex and ends at the last item in the array. Inside of this loop, compare item to the value of the item at the index of the loop we’re currently in. If the value at the index of the child loop is less than item, increment the currentIndexCopy.
  5. Once the loop from step 4 is completed, check to see if the currentIndexCopy has changed. If it has not changed, take a step forward in the loop.
  6. If the value at currentIndexCopy is the same as item, increment currentIndexCopy. This will skip all duplicate values.
  7. Save the item at the currentIndexCopy (we called our temp), place item into the index of currentIndexCopy, and update the value of item to temp.
  8. Create an additional loop that runs until currentIndex and currentIndexCopy are the same.
  9. Inside the loop, save currentIndex to currentIndexCopy.
  10. Repeat steps 4, 6 and 7.

Discussion