Cycle sort is an in-place, unstable sorting algorithm, 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. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Complexity

  • Time: worst , best , average
  • Space: worst auxiliary

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

    console.log(`original array = [${D.join(', ')}]`);

const N = D.length;
let writes = 0; // number of writing performed
let pos; // the index of item in the sorted array
let item; // an item in the array
let temp; // a temp value used for storing swapped item
for (let cycleStart = 0; cycleStart <= N - 2; cycleStart++) {
  item = D[cycleStart];

  // find where to put the item
  pos = cycleStart;

  for (let i = cycleStart + 1; i <= N - 1; i++) {
    
    if (D[i] < item) {
      pos++;
    }
  }

  // if the item is already there, this is not a circle
  if (pos === cycleStart) {
    
    continue;
  }

  // otherwise put the item there or right after any duplicates
  while (item === D[pos]) {
    pos++;
  }

  // write item to new index and increment writes
  temp = D[pos];
  D[pos] = item;
  item = temp;

  writes++;

  if (pos !== cycleStart) {
    console.log(`Rewrite ${D[pos]} to index ${pos}; the next value to rewrite is ${item}`);
  } else {
    console.log(`Rewrite ${D[pos]} to index ${pos}`);
  }

  // rotate the rest of the cycle
  while (pos !== cycleStart) {
    pos = cycleStart;

    for (let i = cycleStart + 1; i <= N - 1; i++) {
      
      if (D[i] < item) {
        pos++;
      }
    }

    while (item === D[pos]) {
      pos++;
    }

    temp = D[pos];
    D[pos] = item;
    item = temp;

    if (pos !== cycleStart) {
      console.log(`Rewrite ${D[pos]} to index ${pos}; the next value to rewrite is ${item}`);
    } else {
      console.log(`Rewrite ${D[pos]} to index ${pos}`);
    }

    writes++;
  }
}

console.log(`Number of writes performed is ${writes}`);