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 on within the viz to run it again.

forked from HarryStevens's block: Radix Sort

forked from lorenzopub's block: Radix Sort

<!DOCTYPE html>
<html>
<head>
	<style>
	body {
		font-family: "Helvetica Neue", sans-serif;
	}
	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 margin = {top: 0, bottom: 0, left: r + 10, right: r + 10},
		width = window.innerWidth - margin.left - margin.right,
		height = window.innerHeight - margin.top - margin.bottom;

var svg = d3.select("#viz").append("svg")
			.attr("width", width + margin.left + margin.right)
			.attr("height", height + margin.top + margin.bottom)
		.append("g")
			.attr("transform", `translate(${margin.left}, ${margin.top})`);

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