// C++ program to implement cycle sort #include    using namespace std; // Function sort the array using Cycle sort void cycleSort(int arr[] int n) {  // count number of memory writes  int writes = 0;  // traverse array elements and put it to on  // the right place  for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) {  // initialize item as starting point  int item = arr[cycle_start];  // Find position where we put the item. We basically  // count all smaller elements on right side of item.  int pos = cycle_start;  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos++;  // If item is already in correct position  if (pos == cycle_start)  continue;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (pos != cycle_start) {  swap(item arr[pos]);  writes++;  }  // Rotate rest of the cycle  while (pos != cycle_start) {  pos = cycle_start;  // Find position where we put the element  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos += 1;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (item != arr[pos]) {  swap(item arr[pos]);  writes++;  }  }  }  // Number of memory writes or swaps  // cout << writes << endl ; } // Driver program to test above function int main() {  int arr[] = { 1 8 3 9 10 10 2 4 };  int n = sizeof(arr) / sizeof(arr[0]);  cycleSort(arr n);  cout << 'After sort : ' << endl;  for (int i = 0; i < n; i++)  cout << arr[i] << ' ';  return 0; } 

// Java program to implement cycle sort import java.util.*; import java.lang.*; class GFG {  // Function sort the array using Cycle sort  public static void cycleSort(int arr[] int n)  {  // count number of memory writes  int writes = 0;  // traverse array elements and put it to on  // the right place  for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) {  // initialize item as starting point  int item = arr[cycle_start];  // Find position where we put the item. We basically  // count all smaller elements on right side of item.  int pos = cycle_start;  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos++;  // If item is already in correct position  if (pos == cycle_start)  continue;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (pos != cycle_start) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  // Rotate rest of the cycle  while (pos != cycle_start) {  pos = cycle_start;  // Find position where we put the element  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos += 1;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (item != arr[pos]) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }  // Driver program to test above function  public static void main(String[] args)  {  int arr[] = { 1 8 3 9 10 10 2 4 };  int n = arr.length;  cycleSort(arr n);  System.out.println('After sort : ');  for (int i = 0; i < n; i++)  System.out.print(arr[i] + ' ');  } } // Code Contributed by Mohit Gupta_OMG <(0_o)> 

# Python program to implement cycle sort def cycleSort(array): writes = 0 # Loop through the array to find cycles to rotate. for cycleStart in range(0 len(array) - 1): item = array[cycleStart] # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # 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 == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycleStart: # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # Put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 return writes # driver code  arr = [1 8 3 9 10 10 2 4 ] n = len(arr) cycleSort(arr) print('After sort : ') for i in range(0 n) : print(arr[i] end = ' ') # Code Contributed by Mohit Gupta_OMG <(0_o)> 

// C# program to implement cycle sort using System; class GFG {    // Function sort the array using Cycle sort  public static void cycleSort(int[] arr int n)  {  // count number of memory writes  int writes = 0;  // traverse array elements and   // put it to on the right place  for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++)  {  // initialize item as starting point  int item = arr[cycle_start];  // Find position where we put the item.   // We basically count all smaller elements   // on right side of item.  int pos = cycle_start;  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos++;  // If item is already in correct position  if (pos == cycle_start)  continue;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (pos != cycle_start) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  // Rotate rest of the cycle  while (pos != cycle_start) {  pos = cycle_start;  // Find position where we put the element  for (int i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos += 1;  // ignore all duplicate elements  while (item == arr[pos])  pos += 1;  // put the item to it's right position  if (item != arr[pos]) {  int temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }  // Driver program to test above function  public static void Main()  {  int[] arr = { 1 8 3 9 10 10 2 4 };  int n = arr.Length;    // Function calling  cycleSort(arr n);  Console.WriteLine('After sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by Nitin Mittal 

<script> // Javascript program to implement cycle sort  // Function sort the array using Cycle sort  function cycleSort(arr n)  {    // count number of memory writes  let writes = 0;    // traverse array elements and put it to on  // the right place  for (let cycle_start = 0; cycle_start <= n - 2; cycle_start++)  {    // initialize item as starting point  let item = arr[cycle_start];    // Find position where we put the item. We basically  // count all smaller elements on right side of item.  let pos = cycle_start;  for (let i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos++;    // If item is already in correct position  if (pos == cycle_start)  continue;    // ignore all duplicate elements  while (item == arr[pos])  pos += 1;    // put the item to it's right position  if (pos != cycle_start)  {  let temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }    // Rotate rest of the cycle  while (pos != cycle_start)  {  pos = cycle_start;    // Find position where we put the element  for (let i = cycle_start + 1; i < n; i++)  if (arr[i] < item)  pos += 1;    // ignore all duplicate elements  while (item == arr[pos])  pos += 1;    // put the item to it's right position  if (item != arr[pos]) {  let temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }   // Driver code   let arr = [ 1 8 3 9 10 10 2 4 ];  let n = arr.length;  cycleSort(arr n);    document.write('After sort : ' + '  
');  for (let i = 0; i < n; i++)  document.write(arr[i] + ' ');    // This code is contributed by susmitakundugoaldanga. </script> 

#include    using namespace std; void cyclicSort(int arr[] int n){  int i = 0;   while(i < n)  {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correct = arr[i] - 1 ;  if(arr[i] != arr[correct]){  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr[i] arr[correct]) ;  }else{  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++ ;  }  } } void printArray(int arr[] int size) {  int i;  for (i = 0; i < size; i++)  cout << arr[i] << ' ';  cout << endl; } int main() {  int arr[] = { 3 2 4 5 1};  int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Before sorting array: n';  printArray(arr n);  cyclicSort(arr n);  cout << 'Sorted array: n';  printArray(arr n);  return 0; } 

// java program to check implement cycle sort import java.util.*; public class MissingNumber {  public static void main(String[] args)  {  int[] arr = { 3 2 4 5 1 };  int n = arr.length;  System.out.println('Before sort :');  System.out.println(Arrays.toString(arr));  CycleSort(arr n);    }  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  System.out.println('After sort : ');  System.out.print(Arrays.toString(arr));      }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  } } // this code is contributed by devendra solunke 

# Python program to check implement cycle sort def cyclicSort(arr n): i = 0 while i < n: # as array is of 1 based indexing so the # correct position or index number of each # element is element-1 i.e. 1 will be at 0th # index similarly 2 correct index will 1 so # on... correct = arr[i] - 1 if arr[i] != arr[correct]: # if array element should be lesser than # size and array element should not be at # its correct position then only swap with # its correct position or index value arr[i] arr[correct] = arr[correct] arr[i] else: # if element is at its correct position # just increment i and check for remaining # array elements i += 1 def printArray(arr): print(*arr) arr = [3 2 4 5 1] n = len(arr) print('Before sorting array:') printArray(arr) # Function Call cyclicSort(arr n) print('Sorted array:') printArray(arr) # This Code is Contributed by Prasad Kandekar(prasad264) 

using System; public class GFG {  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  Console.Write('nAfter sort : ');  for (int index = 0; index < n; index++)  Console.Write(arr[index] + ' ');  }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  }  static public void Main()  {  // Code  int[] arr = { 3 2 4 5 1 };  int n = arr.Length;  Console.Write('Before sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  CycleSort(arr n);  } } // This code is contributed by devendra solunke 

// JavaScript code for the above code function cyclicSort(arr n) {  var i = 0;  while (i < n)  {    // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  let correct = arr[i] - 1;  if (arr[i] !== arr[correct])  {    // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  [arr[i] arr[correct]] = [arr[correct] arr[i]];  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  } } function printArray(arr size) {  for (var i = 0; i < size; i++) {  console.log(arr[i] + ' ');  }  console.log('n'); } var arr = [3 2 4 5 1]; var n = arr.length; console.log('Before sorting array: n'); printArray(arr n); cyclicSort(arr n); console.log('Sorted array: n'); printArray(arr n); // This Code is Contributed by Prasad Kandekar(prasad264)