Skip to content

Instantly share code, notes, and snippets.

@lukeo357
Last active August 14, 2022 18:01
Show Gist options
  • Save lukeo357/4af58d09021899f14dfa585df6c86df6 to your computer and use it in GitHub Desktop.
Save lukeo357/4af58d09021899f14dfa585df6c86df6 to your computer and use it in GitHub Desktop.
LSD Radix sort with JavaScript
/* A Queue based datastructure for implementing our radix algorithm.
Sorting will modify the existing input data and return the sorted data */
function Queue(){
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.isEmpty = isEmpty;
};
function enqueue(element){
this.dataStore.push(element);
};
function dequeue(){
if(this.dataStore.length == 0){
return false;
} else {
return this.dataStore.shift();
}
};
function isEmpty(){
if(this.dataStore.length == 0){
return true;
} else {
return false;
}
};
/* This particular radix function will sort positive integers of value range 0 - 99
Though it is easily scale-able to accept a much larger value range with little modification */
function radix(data){
var bin = []; // Used to hold our array of queues
var digIndex = []; // This will be used to hold mapping values for remapping data elements to their proper index location
for(var i = 0; i < 10; i++){
bin[i] = new Queue();
}; // Block 1------------------------------
for(var i = 0; i < data.length; i++){
bin[data[i]%10].enqueue(data[i]); // The first enqueue process is a forward sweep
};
for(var i = 0; i < bin.length; i++){
digIndex.push(bin[i].dataStore.length);
};
for(var i = 0; i < digIndex.length - 1; i++){
digIndex[i + 1] += digIndex[i];
};
for(var i = bin.length - 1; i >= 0; i--){
while(!bin[i].isEmpty()){
data[--digIndex[i]] = bin[i].dequeue(); // The first deqeueing process
}
}; // Block 2------------------------------
digIndex = []; // re-initialize digIndex
for(var i = data.length - 1; i >= 0; i--){
bin[Math.floor(data[i]/10)%10].enqueue(data[i]); // The second enqueue process will be a backsweep
};
for(var i = 0; i < bin.length; i++){
digIndex.push(bin[i].dataStore.length);
};
for(var i = 0; i < digIndex.length - 1; i++){
digIndex[i + 1] += digIndex[i];
};
for(var i = bin.length - 1; i >= 0; i--){
while(!bin[i].isEmpty()){
data[--digIndex[i]] = bin[i].dequeue(); // The final dequeue process resulting in the sorted data array
}
};
return data;
};
var test = [1,5,22,67,88,12,99,4,68,71,0];
radix(test);
console.log(test);
/* Below 900,000 random integers of values ranging from 0 - 99 are generated and pushed
to the testA array. The radix sort processes it astonishingly fast(500ms) on a 2013
i5 MacBook Air(4GB DDR3) and this also includes the runtime for generating the random integers
and pushing them to the testA array. So the radix sort real runtime for 900,000 integers is more likely near 150ms!*/
var testA = [];
for(var i = 0; i < 900000; i++){
testA.push(Math.floor(Math.random()*100));
}
radix(testA);
console.log(testA);
/* A detailed instructional document on how this radix function works
can be viewed in HTML format here: https://stbean.github.io/JavaScript-LSD-Radix-Documentation */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment