2021-01-25 23:50:46 +05:30
|
|
|
/**
|
|
|
|
|
* 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.
|
2021-01-25 23:52:47 +05:30
|
|
|
*
|
2021-01-25 23:51:09 +05:30
|
|
|
* Wikipedia: https://en.wikipedia.org/wiki/Cycle_sort
|
2021-01-25 23:50:46 +05:30
|
|
|
*/
|
2020-05-04 11:58:44 +05:30
|
|
|
|
2021-10-04 18:49:54 -04:00
|
|
|
/**
|
|
|
|
|
* cycleSort takes an input array of numbers and returns the array sorted in increasing order.
|
|
|
|
|
*
|
|
|
|
|
* @param {number[]} list An array of numbers to be sorted.
|
|
|
|
|
* @return {number[]} An array of numbers sorted in increasing order.
|
|
|
|
|
*/
|
2020-05-03 09:05:12 +02:00
|
|
|
function cycleSort (list) {
|
|
|
|
|
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++
|
|
|
|
|
}
|
|
|
|
|
}
|
2021-10-04 18:49:31 -04:00
|
|
|
// if it is the same, continue
|
2020-05-04 11:58:44 +05:30
|
|
|
if (position === cycleStart) {
|
2020-05-03 09:05:12 +02:00
|
|
|
continue
|
|
|
|
|
}
|
2020-05-04 11:58:44 +05:30
|
|
|
while (value === list[position]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
position++
|
|
|
|
|
}
|
2018-10-22 19:27:31 +02:00
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
const oldValue = list[position]
|
|
|
|
|
list[position] = value
|
|
|
|
|
value = oldValue
|
|
|
|
|
|
|
|
|
|
// rotate the rest
|
2020-05-04 11:58:44 +05:30
|
|
|
while (position !== cycleStart) {
|
2020-05-03 09:05:12 +02:00
|
|
|
position = cycleStart
|
|
|
|
|
for (let i = cycleStart + 1; i < list.length; i++) {
|
|
|
|
|
if (list[i] < value) {
|
|
|
|
|
position++
|
2018-10-22 19:27:31 +02:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2020-05-04 11:58:44 +05:30
|
|
|
while (value === list[position]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
position++
|
|
|
|
|
}
|
|
|
|
|
const oldValueCycle = list[position]
|
|
|
|
|
list[position] = value
|
|
|
|
|
value = oldValueCycle
|
2018-10-22 19:27:31 +02:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2021-10-04 18:53:03 -04:00
|
|
|
return list
|
2018-10-22 19:27:31 +02:00
|
|
|
}
|
2021-01-25 23:51:55 +05:30
|
|
|
|
2021-10-04 18:50:14 -04:00
|
|
|
export { cycleSort }
|
