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