W10D4.js

//Write an O(n) algorithm to sort an array of integers, where you know in
//advance what the lowest and highest values are.
function bucket_sort(arr, min, max) {
	var buckets = Array(max - min + 1);
	for (var i = 0; i < arr.length; ++i)
		buckets[arr[i] - min] = (buckets[arr[i] - min]|0) + 1;
	var ret = [];
	for (var i = min; i <= max; ++i)
		for (var j = 0; j < buckets[i - min]; ++j)
			ret.push(i);
	return ret;
}

//Write an algorithm to shuffle an array into a random order
//in-place (i.e. without creating a new array).
function shuffle(arr) {
	//Swap every element with a randomly-chosen one. On average, each
	//element will be moved twice; every element will be moved at least
	//once, but some will be moved three times or more.
	for (var i = 0; i < arr.length; ++i) {
		var j = Math.floor(Math.random() * arr.length);
		var tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	return arr;
}

//Imagine that I gave you twenty books to sort in alphabetical order. How
//would you go about it? Can you express this as an algorithm?
function insertion_sort(arr) {
	//1) Set aside a shelf or bit of table space to do the sorting.
	var ret = [];
	//2) Grab a book and put it onto the shelf.
	//3) Grab the next book, and place it either left or right of the
	//   first book, according to position.
	//4) Grab the third, and put it left, between, or right.
	//5) Continue until you have no more books.
	for (var i = 0; i < arr.length; ++i) {
		//Insert arr[i] into ret at the appropriate position.
		var j;
		//(Note the use of <= here rather than <, to give stability.)
		for (j = 0; j < ret.length && ret[j] <= arr[i]; ++j);
		//We let Array.splice() do the actual insertion work. But be
		//aware that this can be an expensive operation.
		ret.splice(j, 0, arr[i]);
	}
	return ret;
}


//Tests for the above functions
var arr = []; for (var i=0; i<20; ++i) arr.push(Math.floor(Math.random()*10));
console.log("Random array:", arr);
console.log("Bucket sort: ", bucket_sort(arr, 0, 10));
console.log("Shuffle:     ", shuffle(arr));
console.log("Insert sort: ", insertion_sort(arr));

//Notes:
//Insertion sort is pretty sucky when performed on a vanilla array. It's better
//if you use a linked list, but even so, it's never going to be better than
//O(N log N), because it's a naive comparison sort; and Quicksort has superior
//overall performance and the same algorithmic complexity. However, insertion
//sort can be used to great effect in hybrid algorithms such as Timsort (the
//standard sorting algorithm of several languages including Python, for which
//it was first developed (by Tim Peters, hence the name)), which can boast a
//best-case of O(N) and a worst case of O(N log N), significantly better than
//quicksort's O(N log N) and O(N^2). https://en.wikipedia.org/wiki/Timsort
//Hybrid algorithms are more complicated to explain than simple ones, but are
//far better at coping with real-world data; for instance, it's plausible to
//quicksort large arrays, but for those below (say) ten elements, bubble sort
//instead. Bubble sort isn't bad for short arrays - it just has terrible Big O,
//which means it's abysmal on large arrays :)