サイクルソート

GfG Practice で試してみる

サイクルソートは、インプレースの不安定なソートアルゴリズムであり、値の範囲が狭い要素を含む配列をソートする場合に特に役立ちます。 W. D. ジョーンズによって開発され、1963 年に公開されました。

サイクルソートの背後にある基本的な考え方は、入力配列をサイクルに分割し、各サイクルがソートされた出力配列内の同じ位置に属する要素で構成されるようにすることです。次に、アルゴリズムは一連のスワップを実行して、すべてのサイクルが完了し、配列がソートされるまで、サイクル内の正しい位置に各要素を配置します。

ここでは、サイクルソートアルゴリズムを段階的に説明します。

n 要素のソートされていない配列から始めます。
変数cycleStartを0に初期化します。
配列内の各要素について、その右側にある他のすべての要素と比較します。現在の要素よりも小さい要素がある場合は、cycleStart を増分します。
最初の要素と他のすべての要素を比較した後、cycleStart がまだ 0 である場合は、次の要素に移動して手順 3 を繰り返します。
より小さい要素が見つかったら、現在の要素をそのサイクルの最初の要素と交換します。このサイクルは、現在の要素が元の位置に戻るまで継続されます。

すべてのサイクルが完了するまで、ステップ 3 ～ 5 を繰り返します。

これで配列がソートされました。

サイクルソートの利点の 1 つは、配列をインプレースでソートするためメモリフットプリントが低く、一時変数やバッファ用に追加のメモリを必要としないことです。ただし、特定の状況、特に入力配列の値の範囲が広い場合には速度が低下する可能性があります。それにもかかわらず、サイクルソートは、値の範囲が制限された小さな配列をソートする場合など、特定の状況では依然として便利なソートアルゴリズムです。

サイクルソートはインプレースソートアルゴリズムです不安定なソートアルゴリズムもう 1 つは、元の配列への書き込みの総数という観点から理論的に最適な比較ソートです。

メモリ書き込み回数の点で最適です。それメモリへの書き込み回数を最小限に抑えるソートする (各値は、すでに正しい位置にある場合は 0 回書き込まれるか、正しい位置に 1 回書き込まれます。)
これは、ソートされる配列をサイクルに分割できるという考えに基づいています。サイクルをグラフとして視覚化できます。 i 番目のインデックスの要素がソートされた配列の j 番目のインデックスに存在する必要がある場合、n 個のノードとノード i からノード j に向かうエッジがあります。
arr[] のサイクル = {2 4 5 1 3}

arr[] のサイクル = {2 4 5 1 3}

arr[] のサイクル = {4 3 2 1}

arr[] のサイクル = {4 3 2 1}

すべてのサイクルを 1 つずつ検討します。まず最初の要素を含むサイクルを考えます。最初の要素の正しい位置を見つけて、それを正しい位置 (たとえば j) に配置します。 arr[j] の古い値を考慮してその正しい位置を見つけます。現在のサイクルのすべての要素が正しい位置に配置されるまで、つまりサイクルの開始点に戻らないまでこれを続けます。

疑似コード:

 Begin   
 for   
 start:= 0 to n - 2 do   
 key := array[start]   
 location := start   
 for i:= start + 1 to n-1 do   
  if array[i]  < key then   
  location: =location +1   
 done   
 if location = start then   
  ignore lower part go for next iteration   
 while key = array[location] do   
  location: = location + 1   
 done   
 if location != start then   
  swap array[location] with key   
 while location != start do   
  location start   
  
  
 for i:= start + 1 to n-1 do   
  if array[i]  < key then   
  location: =location +1   
 done   
 while key= array[location]   
  location := location +1   
  if key != array[location]   
  Swap array[location] and key   
  done   
  done   
 End      説明 ：       
   arr[] = {10 5 2 3}   
  index = 0 1 2 3   
 cycle_start = 0    
    item     = 10 = arr[0]   
  
 Find position where we put the item    
 pos = cycle_start   
 i=pos+1   
 while(i   
 if (arr[i]  < item)    
  pos++;   
  
 We put 10 at arr[3] and change item to    
 old value of arr[3].   
 arr[] = {10 5 2        10      }    
    item     = 3    
  
 Again rotate rest cycle that start with      index '0'      
 Find position where we put the item = 3    
 we swap item with element at arr[1] now    
 arr[] = {10        3       2        10      }    
    item     = 5   
  
 Again rotate rest cycle that start with index '0' and item = 5    
 we swap item with element at arr[2].   
 arr[] = {10        3              5              10       }    
    item     = 2   
  
 Again rotate rest cycle that start with index '0' and item = 2   
 arr[] = {       2              3                      5              10      }    
  
 Above is one iteration for cycle_stat = 0.   
 Repeat above steps for cycle_start = 1 2 ..n-2   上記のアプローチの実装を以下に示します。  
 CPP      // 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      // 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)>   
  Python3      # 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#      // 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   
  JavaScript       <  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>   
    
  出力   After sort : 1 2 3 4 8 9 10 10  
     時間計算量の分析    :   
      最悪の場合:    の上  ² )   
     平均的なケース:    の上  ² )   
     最良のケース:    の上  ² ）  
 
     補助スペース:    ○(1)  
   このアルゴリズムが導入されているため、空間の複雑さは一定であり、並べ替えに余分なメモリを使用しません。  
 
     方法 2:    このメソッドは、指定された配列の値または要素が 1 から N または 0 から N の範囲にある場合にのみ適用できます。このメソッドでは、配列を回転する必要はありません。  
     アプローチ ：    指定されたすべての配列値は 1 から N または 0 から N の範囲内である必要があります。範囲が 1 から N の場合、すべての配列要素の正しい位置はインデックス == 値-1 になります。つまり、0 番目のインデックス値は 1 になり、同様に 1 番目のインデックス位置の値は 2 になり、以下同様に n 番目の値まで続きます。  
  同様に、0 から N の値についても、各配列要素または値の正しいインデックス位置はその値と同じになります。つまり、0 番目のインデックスには 0 が存在し、最初の位置には 1 が存在します。  
     説明 ：     
  arr[] = {5 3 1 4 2}   
 index = 0 1 2 3 4   
  
 i = 0;   
 while( i  < arr.length)   
  correctposition = arr[i]-1;    
     
  find ith item correct position   
  for the first time i = 0 arr[0] = 5 correct index of 5 is 4 so arr[i] - 1 = 5-1 = 4   
     
     
  if( arr[i]  <= arr.length && arr[i] != arr[correctposition])   
     
     
  arr[i] = 5 and arr[correctposition] = 4    
  so 5  <= 5 && 5 != 4 if condition true    
  now swap the 5 with 4    
     
     
  int temp = arr[i];   
  arr[i] = arr[correctposition];   
  arr[correctposition] = temp;   
     
  now resultant arr at this after 1st swap    
  arr[] = {2 3 1 4 5} now 5 is shifted at its correct position    
     
  now loop will run again check for i = 0 now arr[i] is = 2    
  after swapping 2 at its correct position    
  arr[] = {3 2 1 4 5}   
     
  now loop will run again check for i = 0 now arr[i] is = 3    
  after swapping 3 at its correct position    
  arr[] = {1 2 3 4 5}   
     
  now loop will run again check for i = 0 now arr[i] is = 1   
  this time 1 is at its correct position so else block will execute and i will increment i = 1;   
  once i exceeds the size of array will get array sorted.   
  arr[] = {1 2 3 4 5}   
     
     
  else   
     
  i++;   
 loop end;   
  
 once while loop end we get sorted array just print it    
 for( index = 0 ; index  < arr.length; index++)   
  print(arr[index] + ' ')   
 sorted arr[] = {1 2 3 4 5}   上記のアプローチの実装を以下に示します。  
 C++      #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      // 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      # 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)   
  C#      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      // 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)   
    
  出力   Before sorting array: 3 2 4 5 1 Sorted array: 1 2 3 4 5  
     時間計算量の分析:    
      最悪の場合:    の上）   
     平均的なケース:    の上）   
     最良のケース:    の上）  
 
     補助スペース:    ○(1)  
     サイクルソートの利点:    
   追加のストレージは必要ありません。  
   インプレースソートアルゴリズム。  
   メモリへの最小書き込み回数  
   サイクル ソートは、配列が EEPROM またはフラッシュに保存されている場合に便利です。   
 
     サイクルソートの欠点:    
    ほとんど使用されません。  
   時間計算量がより多くなります o(n^2)  
   ソートアルゴリズムが不安定です。  
 
     サイクルソートの適用:    
   このソート アルゴリズムは、メモリの書き込みまたはスワップ操作にコストがかかる状況に最適です。  
  複雑な問題に役立ちます。    
    
 
         クイズの作成