Cycle Sort in C++

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


cycle-sort in C++

#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 << ", ";
    }
}

Discussion