| license: gpl-3.0 |
I've been working through Data Structures and Algorithms with Javascript and thought it might be fun to try and visualize the radix sort algorithm described in chapter 5.
The algorithm works by first grouping a list of integers by their right-most digit, and then moving left.
Click anywhere within the frame to run it again.
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <style> | |
| body { | |
| font-family: "Helvetica Neue", sans-serif; | |
| margin: 0; | |
| } | |
| text { | |
| fill: #000; | |
| text-shadow: 1px 1px 1px #fcfcfc, 1px 1px 1px #eee, 0 -1px 0 #fff, -1px 0 0 #fff; | |
| text-anchor: middle; | |
| } | |
| circle { | |
| stroke: #000; | |
| stroke-width: 2px; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div id="viz"></div> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/chroma-js/1.3.4/chroma.min.js"></script> | |
| <script src="Q.js"></script> | |
| <script src="https://unpkg.com/d3-marcon/build/d3-marcon.min.js"></script> | |
| <script> | |
| run(); | |
| document.getElementById("viz").onclick = function(){ | |
| document.getElementById("viz").innerHTML = ""; | |
| run(); | |
| }; | |
| function run(){ | |
| var r = window.innerWidth / 25, | |
| d = 2000, | |
| delay = d / 20; | |
| var m = d3.marcon().top(0).bottom(0).left(r + 10).right(r + 10).width(window.innerWidth).height(window.innerHeight).element("#viz"); | |
| m.render(); | |
| var width = m.innerWidth(), height = m.innerHeight(), svg = m.svg(); | |
| var x = d3.scaleLinear() | |
| .range([0, width]) | |
| .domain([0, 9]); | |
| var z = chroma.scale(chroma.brewer.OrRd) | |
| .domain([0, 100]); | |
| var queues = []; | |
| for (var i = 0; i < 10; ++i){ | |
| queues[i] = new Q(); | |
| } | |
| var nums = []; | |
| for (var i = 0; i < 10; ++i){ | |
| nums[i] = {num: Math.floor(Math.floor(Math.random() * 100)), pos: i}; | |
| } | |
| redraw(nums); | |
| var n = 0; | |
| var int = setInterval(function(){ | |
| if (n == d3.max(nums).toString().length - 1) clearInterval(int); | |
| distribute(nums, queues, n == 0 ? 1 : 10); | |
| collect(queues, nums); | |
| redraw(nums); | |
| n++; | |
| }, d * 2); | |
| function redraw(data){ | |
| // JOIN | |
| var cir = svg.selectAll("circle") | |
| .data(data, function(d){ return d.pos; }); | |
| var txt = svg.selectAll("text") | |
| .data(data, function(d){ return d.pos; }); | |
| // UPDATE | |
| cir.transition() | |
| .duration(d).delay(function(d, i){ return i * delay; }) | |
| .attr("cx", function(d, i){ return x(i); }); | |
| txt.transition() | |
| .duration(d).delay(function(d, i){ return i * delay; }) | |
| .attr("x", function(d, i){ return x(i); }) | |
| // ENTER | |
| cir.enter().append("circle") | |
| .attr("fill", function(d){ return z(d.num); }) | |
| .attr("r", r) | |
| .attr("cx", width / 2) | |
| .attr("cy", -r) | |
| .transition().duration(d / 2).delay(function(d, i){ return i * delay / 2; }) | |
| .attr("cx", function(d, i){ return x(i); }) | |
| .attr("cy", height / 2) | |
| txt.enter().append("text") | |
| .text(function(d){ return d.num; }) | |
| .attr("dy", 3) | |
| .attr("x", width / 2) | |
| .attr("y", -r) | |
| .transition().duration(d / 2).delay(function(d, i){ return i * delay / 2; }) | |
| .attr("x", function(d, i){ return x(i); }) | |
| .attr("y", height / 2); | |
| } | |
| // RADIX SORT | |
| // Distribute numbers by the place (1s or 10s) digit: | |
| function distribute(nums, queues, digit){ | |
| for (var i = 0; i < nums.length; ++i){ | |
| if (digit == 1){ | |
| queues[nums[i].num % 10].enq(nums[i]); | |
| } else { | |
| queues[Math.floor(nums[i].num / 10)].enq(nums[i]); | |
| } | |
| } | |
| } | |
| // Collect numbers from the queues: | |
| function collect(queues, nums){ | |
| var i = 0; | |
| for (var digit = 0; digit < 10; ++digit){ | |
| while (!queues[digit].isEmpty()){ | |
| nums[i++] = queues[digit].deq(); | |
| } | |
| } | |
| } | |
| } | |
| </script> | |
| </body> | |
| </html> |
| function Q(){ | |
| this.data = []; | |
| this.enq = enq; | |
| this.deq = deq; | |
| this.isEmpty = isEmpty; | |
| } | |
| function enq(el){ | |
| typeof(el) == "object" && el.length >= 0 ? this.data = this.data.concat(el) : this.data.push(el); | |
| } | |
| function deq(){ | |
| return this.data.shift(); | |
| } | |
| function isEmpty(){ | |
| return this.data.length == 0 ? true : false; | |
| } |
