C++ Program for Cycle Sort?

What is Cycle Sort?

Cycle sort is an in-place, unstable sorting algorithm. It is a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm.

A sorting algorithm is in-place sorting in which the sorted items occupy the same place as the original one.

Key Points of Cycle Sort

Following are the key points:

• It is optimal in terms of number of memory writes. It minimize the number of memory write to sort (Each value is either written zero times, if it's already in its correct position, or written one time to its correct position.)
• It operates on the belief that the array to be sorted can be divided into cycles. Cycles can be represented as graphs. We have n nodes and an edge directed from node i to node j if the element at the ith index must be present at the jth index in the sorted array.

Example Scenario

Let's see the following example scenario and its diagram:

Input: arr[] = {7, 4, 3, 5, 2, 1, 6}
Output: 1, 2, 3, 4, 5, 6, 7

Input: arr[] = {4, 3, 2, 1}
Output: 1, 2, 3, 4

C++ Program for Cycle Sort

In the following example, we implement a C++ program to implement cycle sort:

#include<iostream>
using namespace std;
void cycleSort(int a[], int n) {
   int writes = 0;
   for (int c_start = 0; c_start <= n - 2; c_start++) {
      int item = a[c_start];
      int pos = c_start;
      for (int i = c_start + 1; i < n; i++)
         if (a[i] < item)
            pos++;
      if (pos == c_start)
         continue;
      while (item == a[pos])
         pos += 1;
      if (pos != c_start) {
            swap(item, a[pos]);
            writes++;
      }
      while (pos != c_start) {
         pos = c_start;
         for (int i = c_start + 1; i < n; i++)
            if (a[i] < item)
         pos += 1;
         while (item == a[pos])
            pos += 1;
         if (item != a[pos]) {
            swap(item, a[pos]);
            writes++;
         }
      }
   }
}

int main() {
   int a[] ={7, 4, 3, 2, 1, 6};
   int n = sizeof(a) / sizeof(a[0]);
   cycleSort(a, n);
   for (int i = 0; i < n; i++)
      cout << a[i] << " ";
   return 0;
}

Following is the output:

1 2 3 4 6 7