Radix Sort

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>

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>

https://d3js.org/d3.v4.min.js

https://cdnjs.cloudflare.com/ajax/libs/chroma-js/1.3.4/chroma.min.js

https://unpkg.com/d3-marcon/build/d3-marcon.min.js