forked from TheAlgorithms/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CycleSort.js
67 lines (61 loc) · 1.7 KB
/
CycleSort.js
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
/**
* 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.
*
* Wikipedia: https://en.wikipedia.org/wiki/Cycle_sort
*/
function cycleSort (list) {
let writes = 0
for (let cycleStart = 0; cycleStart < list.length; cycleStart++) {
let value = list[cycleStart]
let position = cycleStart
// search position
for (let i = cycleStart + 1; i < list.length; i++) {
if (list[i] < value) {
position++
}
}
// if its the same continue
if (position === cycleStart) {
continue
}
while (value === list[position]) {
position++
}
const oldValue = list[position]
list[position] = value
value = oldValue
writes++
// rotate the rest
while (position !== cycleStart) {
position = cycleStart
for (let i = cycleStart + 1; i < list.length; i++) {
if (list[i] < value) {
position++
}
}
while (value === list[position]) {
position++
}
const oldValueCycle = list[position]
list[position] = value
value = oldValueCycle
writes++
}
}
return writes
}
/**
* Implementation of Cycle Sort
*/
const array = [5, 6, 7, 8, 1, 2, 12, 14]
// Before Sort
console.log('\n- Before Sort | Implementation of Cycle Sort -')
console.log(array)
// After Sort
console.log('- After Sort | Implementation of Cycle Sort -')
console.log(cycleSort(array))
console.log('\n')