Bogosort is a sorting algorithm that is intentionally bad, it’s massively inefficient but it will sort numbers into their ordered form. Any improvements made to Bogosort should be equally as inefficient, so let’s improve Bogosort.
What is Bogosort?
Before we begin let’s look at an example of Bogosort written in Javascript
function Bogosort(array){
var isSorted = function(array){
for(var i = 1; i < array.length; i++){
if (array[i-1] > array[i]) {
return false;
}
}
return true;
}
// Fisher-Yates Shuffle
var shuffle = function(array){
var count = array.length, temp, index;
while(count > 0){
index = Math.floor(Math.random() * count);
count--;
temp = array[count];
array[count] = array[index];
array[index] = temp;
}
return array;
}
var sort = function(array){
var sorted = false;
while(!sorted){
array = shuffle(array);
sorted = isSorted(array);
}
return array;
}
return sort(array);
}
Calling Bogosort([5, 2, 1, 3]);
it will iteratively shuffle the array then do a test to see if the result is in order, if not, this process will repeat. We could use a more efficient sorting method, but lets not, let us improve Bogosort but introducing Web Workers.
Web Workers
You can think of Web Workers of introducing multiple threads to a web environment. It’s possible to spin up a new Web Worker that can process a long running task in JavaScript without hindering the performance of the perceived UI / front end.
Note: Web Workers are unable to directly interact with the DOM, but messages can be sent to and from them.
Given that sorting 10 items takes on average 582 ms is it possible to improve by having multiple web workers assist in sorting the array?
Web Worker Bogosort
With a small modification it’s possible to move the bogosort method out into a callable web worker. We append the following to the Bogosort method and move it into it’s own file:
onmessage = function(e){
if (e.data === "stop") {
self.close();
}
else {
self.postMessage(Bogosort(e.data));
}
};
Note:
.postMessage()
is how we can send messages back to the original caller.
Finally, we can spawn two new Workers with the following.
var unsorted = [5, 1, 3, 23, 63, 42, 52, 85, 256, 82];
var workerOne = new Worker("bogoworker.js");
var workerTwo = new Worker("bogoworker.js");
workerOne.onmessage = function(e) {
workerTwo.postMessage("stop");
console.log(e.data);
};
workerTwo.onmessage = function(e) {
workerOne.postMessage("stop");
console.log(e.data);
};
workerOne.postMessage(unsorted);
workerTwo.postMessage(unsorted);
Both workers are created with new Worker("bogoworker.js");
we add a .onmessage
function to each newly created web worker, this function will send a message to the other worker to stop and finally log the result from the sorting.
With this new structure, will it improve the average speed over 10 runs?
211 ms average!
A 371 ms difference! A huge improvement!
…OK so what can we take away from this? If your solution is slow and inefficient throw more resources at it until the problem goes away.