Javascript Quicksort implementation with dynamic comparator.

[javascript]
Array.prototype.swap=function(a, b)
{
var tmp=this[a];
this[a]=this[b];
this[b]=tmp;
}

function quickSort(array,comparator) {
qsort(array,0,array.length,comparator);
}

/**
* NOTE: the comparator is a dynamic function you will define
like so comparator(a,b) {
if (a > b) return 1;
else if (a < b) return -1;
else {
return 0;
}
}
* it is up to you to determine the comparison logic between the elements.
* it’s particularly useful if you’re comparing objects and different properties
* inside them.
*/
function qsort(array, begin, end, comparator)
{
if(end-1>begin) {
var pivot=begin+Math.floor(Math.random()*(end-begin));

pivot=partition(array, begin, end, pivot, comparator);

qsort(array, begin, pivot, comparator);
qsort(array, pivot+1, end, comparator);
}
}

function partition(array, begin, end, pivot, comparator) {
var piv=array[pivot];
array.swap(pivot, end-1);
var store=begin;
var ix;
for(ix=begin; ix<end-1; ++ix) {
if (piv!=undefined && comparator(piv, array[ix]) < 0) {
array.swap(store, ix);
++store;
}
}
array.swap(end-1, store);

return store;
}
[/javascript]

Submit a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.