Created
May 4, 2017 02:37
-
-
Save gunar/36b6daa6b1a55d2da6e2e83a502c408f to your computer and use it in GitHub Desktop.
Cycle sort implemented in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'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