Below is an example of the Cycle Sort algorithm in C++. See the Cycle Sort page for more information and implementations.
#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 << ", "; } }