Skip to content

Instantly share code, notes, and snippets.

@HarryStevens
Last active Sep 17, 2017
Embed
What would you like to do?
Radix Sort
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment