Skip to content

Instantly share code, notes, and snippets.

@coolaj86
Created Jan 17, 2015
Embed
What would you like to do?
A better bogosort - literally an order of magnitude faster
(function () {
"use strict";
// TOO SLOW
/*
function randomize(items) {
items.sort(function () {
return 0.5 - Math.random();
});
}
*/
// http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
function randomize(array) {
var currentIndex = array.length
, temporaryValue
, randomIndex
;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
function isInOrder(items) {
return items.every(function (x, i) {
var next = items[i + 1]
;
if (undefined === next) {
return true;
}
if (x > next) {
return true;
}
return false;
});
}
function timeBogosort(items) {
var then = process.hrtime()
;
while (!isInOrder(items)) {
randomize(items);
}
return process.hrtime(then);
}
function pad(str) {
str = str.toString();
while (str.length < "000000000".length) {
str = '0' + str;
}
return str;
}
function runTest() {
var items = [42]
, dt
;
console.log("| List Size | Seconds |");
console.log("|----------:|--------:|");
while ((dt = timeBogosort(items)) && dt[0] < 1) {
items.push(Math.round(Math.random() * 10000));
randomize(items);
console.log("|", (items.length - 1), "|", dt[0] + '.' + pad(dt[1]));
}
console.log("|", items.length, "|", dt[0] + '.' + pad(dt[1]));
}
runTest();
}());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment