Skip to content

Instantly share code, notes, and snippets.

@gunar
Created May 4, 2017 02:37
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save gunar/36b6daa6b1a55d2da6e2e83a502c408f to your computer and use it in GitHub Desktop.
Save gunar/36b6daa6b1a55d2da6e2e83a502c408f to your computer and use it in GitHub Desktop.
Cycle sort implemented in JavaScript
'use strict'
// ref https://en.wikipedia.org/wiki/Cycle_sort
const cycleSort = array => {
// last item will already be in place
for (let cycleStart = 0; cycleStart < array.length-1; cycleStart++) {
let item = array[cycleStart]
// find where to put the item
let pos = cycleStart
for (let i = cycleStart + 1; i < array.length; i++) {
// TODO: comparison
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
// TODO: comparison
while (item == array[pos]) { pos++ }
const swap = array[pos]
array[pos] = item // TODO: Write
item = swap
console.log('write')
// rotate the rest of the cycle
while (pos != cycleStart) {
// find where to put the item
pos = cycleStart
for (let i = cycleStart + 1; i < array.length; i++) {
if (array[i] < item) pos += 1
}
// put the item there or right after any duplicates
while (item == array[pos]) {
pos += 1
}
const swap = array[pos]
array[pos] = item
item = swap
}
return array
}
}
console.log(cycleSort([3,2,1,4]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment