Skip to content

Instantly share code, notes, and snippets.

@michellephung
Forked from anonymous/index.html
Last active May 10, 2016 02:35
Show Gist options
  • Save michellephung/7aaeba1337c5614a0f54cc66444abd61 to your computer and use it in GitHub Desktop.
Save michellephung/7aaeba1337c5614a0f54cc66444abd61 to your computer and use it in GitHub Desktop.
radix sort
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
var counter = [[]];
function sortLSD(array, maxDigitSymbols) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = parseInt((array[j] % mod) / dev);
console.log("item: "+array[j]+" bucket: " + bucket);
if (counter[bucket] == null ) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
console.log("--------------------");
var pos = 0;
for (var k = 0; k < counter.length; k++) {
var value = null ;
if (counter[k] != null ) {
console.log("counter["+ k + "] "+counter[k]);
while ((value = counter[k].shift()) != null ) {
console.log("while-- value: " + value+" while-- pos: " + pos);
array[pos++] = value;
}
console.log("-->"+array);
}
}
}
return array;
}
var test = [22,24, 1,2,9,3,2,5,14,66];
test = [1, 20, 24, 30, 3];
console.log(sortLSD(test, 2));
</script>
<script id="jsbin-source-javascript" type="text/javascript">var counter = [[]];
function sortLSD(array, maxDigitSymbols) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = parseInt((array[j] % mod) / dev);
console.log("item: "+array[j]+" bucket: " + bucket);
if (counter[bucket] == null ) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
console.log("--------------------");
var pos = 0;
for (var k = 0; k < counter.length; k++) {
var value = null ;
if (counter[k] != null ) {
console.log("counter["+ k + "] "+counter[k]);
while ((value = counter[k].shift()) != null ) {
console.log("while-- value: " + value+" while-- pos: " + pos);
array[pos++] = value;
}
console.log("-->"+array);
}
}
}
return array;
}
var test = [22,24, 1,2,9,3,2,5,14,66];
test = [1, 20, 24, 30, 3];
console.log(sortLSD(test, 2));</script></body>
</html>
var counter = [[]];
function sortLSD(array, maxDigitSymbols) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = parseInt((array[j] % mod) / dev);
console.log("item: "+array[j]+" bucket: " + bucket);
if (counter[bucket] == null ) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
console.log("--------------------");
var pos = 0;
for (var k = 0; k < counter.length; k++) {
var value = null ;
if (counter[k] != null ) {
console.log("counter["+ k + "] "+counter[k]);
while ((value = counter[k].shift()) != null ) {
console.log("while-- value: " + value+" while-- pos: " + pos);
array[pos++] = value;
}
console.log("-->"+array);
}
}
}
return array;
}
var test = [22,24, 1,2,9,3,2,5,14,66];
test = [1, 20, 24, 30, 3];
console.log(sortLSD(test, 2));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment