quantum bogosort for javascript

qbsort.js

/*jshint forin:true, noarg:true, noempty:true, eqeqeq:true, bitwise:true, undef:true, browser:true, indent:4, maxerr:50 */
/*
qbsort.js - quantum bogosort for javascript
Copyright (C) 3011 Keith Beckman

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

/*

Lightning-fast sort times for survivors! Could be faster, esp for larger sets,
but for obvious reasons, the whole array is walked every time.

This is really just proof-of-concept code. QJAX is still kinda new, and browser
support is lacking: you'll probably need bleeding-edge nightlies of most browsers.
Firefox supports it ootb, though, and IE _sort of_ does. MS STILL can't get
standards right, hence the crappy wrapper function around QuantumRequest. Grrr...

Usermode permissions sometimes can block access to system qcalls, so you'll
have to turn off Firefox extensions like NoQ and Paranoid to try this out, and
run the browser as root if you have SELinux enabled.

And yes, I know I shouldn't extend Array.prototype. But this is just toy code, and
everyone's always done it anyway. :-P

done: take a comparison callback
todo: what if I just want to sort numbers or strings, and don't need a cb?
todo: need to handle alternative math generally, rather than just dying unless 1=1
todo: is_sorted could be more efficient
todo: make jshint shut up http://www.jshint.com/reports/70009

*/

function InvalidUniverseException (msg) {
	this.message = msg;
	this.toString = function () {
		return 'InvalidUniverseException: ' + msg;
	};
}

window.getQuantumRequest = function () {
	// QuantumRequest factory for IE compatibility. !!*&% MS
	if (window.QuantumRequest) return new window.QuantumRequest;
	try {
		return new ActiveXObject('MSQUANT2.QUANTREQ.3.0');
	} catch (ex) {
		return null;
	}	
};

Array.prototype.shuffle = function() {
	for (var i = 0, n = this.length; i < n; i++) {
		var j = i, k = i, t;
		while (j == i || k == i || j == k) {
			j = Math.floor(Math.random() * n);
			k = Math.floor(Math.random() * n);
		}
		t = this[j];
		this[j] = this[k];
		this[k] = t;
	}
};

Array.prototype.is_sorted = function(cmp) {
	for (var i = 1, n = this.length; i < n; i++) {
//		if (this[i] < this[i-1]) return false;
		if (!cmp(this[i], this[i-1])) return false;
	}
	return true;
};

Array.prototype.qbsort = function(cmp) {
	if (1 != 1) throw new InvalidUniverseException('1 != 1.'); // todo: handle this with custom equality comparer
	this.shuffle();
	if(!this.is_sorted(cmp)) window.getQuantumRequest().destroyUniverse();
};