Cycle sort

general
,
1

Can anyone tell me what is cycle sort and it’s application

2

Cycle Sort(unstable and inplace) is based on the idea that all permutations of an array are products of certain cycles. What do we mean by this is: Consider the permutation of numbers (1 to n) i.e. [4,2,7,6,5,8,1,3]. This permutation is generated by the product of cycles : (1,4,6,8,3,7)(2)(5). 1->4->6->8->3->7 means On the place of 1st element, 4th element will come. 2nd will remain same. On place of 3rd, 7th will come and so on. So, we do the same in the algorithm also. We cycle through each cycle and write ots element to its proper place.

// this loop loops through the array to find cycles to rotate.
// lets say if the array is 4,2,7,6,5,8,1,3 then we start the cycle from 0.
for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) {
  T item = array[cycleStart];

  // Find where to put the item.
  int pos = cycleStart;
  for (int i = cycleStart + 1; i < array.length; i++)
    if (array[i].compareTo(item) < 0) 
           pos++;  // pos for the first cycle run becomes 3 i.e. 3 elements in the array are less than 4.

  // If the item is already there, this is not a cycle.
  if (pos == cycleStart) 
          continue;

  // Otherwise, put the item there or right after any duplicates.
  while (item.equals(array[pos])) pos++;  
  {
    final T temp = array[pos];
    array[pos] = item;
    item = temp;
  }
  writes++;
  // Rotate the rest of the cycle , till here for the first cycle, the variable item now get its //value as array[3] i.e. 6. We, now ietrate for 6 in the same cycle and then go to the next element //of the cycle.
  while (pos != cycleStart) {
    // Find where to put the item.
    pos = cycleStart;
    for (int i = cycleStart + 1; i < array.length; i++)
      if (array[i].compareTo(item) < 0) pos++;

    // Put the item there or right after any duplicates.
    while (item.equals(array[pos])) pos++;
    {
      final T temp = array[pos];
      array[pos] = item;
      item = temp;
    }
    writes++;
  }
} 
return writes;

The algorithm is famous because of the fact that it makes minimum number of writes to the memory and hence efficient when array is stored in EEPROM or Flash. There is no other algorithm with less data movement.