Cycle Sort

Examples

• 0

  Pseudocode Implementation

  edit move example delete share

  0

  (input)
  output = 0
  for cycleStart from 0 to length(array) - 2
      item = array[cycleStart]
      pos = cycleStart
      for i from cycleStart + 1 to length(array) - 1
          if array[i] < item:
              pos += 1
      if pos == cycleStart:
          continue
      while item == array[pos]:
          pos += 1
      array[pos], item = item, array[pos]
      writes += 1
      while pos != cycleStart:
          pos = cycleStart
          for i from cycleStart + 1 to length(array) - 1
              if array[i] < item:
                  pos += 1
          while item == array[pos]:
              pos += 1
          array[pos], item = item, array[pos]
          writes += 1
  return outout
  

  created Oct 22 at 20:38

  
• -1

  C# Implementation

  edit move example delete share

  -1

  public class CycleSort
  {
      public static void SortCycle(int[] input)
      {
          for (var i = 0; i < input.Length; i++)
          {
              var item = input[i];
              var position = i;
              do
              {
                  var k = input.Where((t, j) => position != j && t < item).Count();
                  if (position == k) continue;
                  while (position != k && item == input[k])
                  {
                      k++;
                  }
                  var temp = input[k];
                  input[k] = item;
                  item = temp;
                  position = k;
              } while (position != i);
          }
      }
  
      public static int[] Main(int[] input)
      {
          SortCycle(input);
          return input;
      }
  }
  

  created Oct 22 at 20:38

  
• -1

  Cycle Sort Basic Information

  edit move example delete share

  -1

  Cycle Sort is sorting algorithm which uses comparison sort that is theoretically optimal in terms of the total number of writes to original array, unlike any other in-place sorting algorithm. Cycle sort is unstable sorting algorithm. It is based on idea of permutation in which permutations are factored into cycles, which individually rotate and return a sorted output.

  Example of Cycle Sort:

  

  Auxiliary Space: O(1)
  Time Complexity: O(n^2)

  edited Oct 22 at 20:38