Last active
August 14, 2022 18:01
-
-
Save lukeo357/4af58d09021899f14dfa585df6c86df6 to your computer and use it in GitHub Desktop.
LSD Radix sort with 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
| /* 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