I ran into an interesting problem today. I had an array of objects that I wanted sorted on a certain property. My obvious thought didn’t work! (Update: I got a comment below from Peter Michaux who points out a nicer solution, it is included here:)
var obj_arr = [ { age: 21, name: "Larry" },
{ age: 34, name: "Curly" },
{ age: 10, name: "Moe" } ];
obj_arr.sort( function(a,b) { return a.name < b.name; });
obj_arr1.sort(function(a,b) { return a.name < b.name ? -1 :
a.name > b.name ? 1 : 0; });
That kind of frustrated me. Sorting is one of those things I expect to be available in all languages. I don’t want to have to write a sorting algorithm every time I need to sort. So I looked into things, pulled up a Javascript Quicksort Algorithm and manipulated it to support any compare function.
Now that I have the freedom to truly write a compare function that works for objects! I also changed around certain parts of the code I found online to actually extend the Array class and make the extra functions hidden. Take a look at the sample usage:
var arr = [1234, 2346, 21234, 3456, 32134, 3456, 1234, 2345, 23, 42523, 1234, 345];
var obj_arr = [ { age: 21, name: "Larry" },
{ age: 34, name: "Curly" },
{ age: 10, name: "Moe" } ];
arr.quick_sort();
obj_arr.quick_sort(function(a,b) { return a.name < b.name });
obj_arr.quick_sort(function(a,b) { return a.age < b.age });
For those who want to see the code be glad, its free. I carried the copyright with it but its rather loose. Grab the JavaScript Source Here! Enjoy:
Array.prototype.swap=function(a, b) {
var tmp=this[a];
this[a]=this[b];
this[b]=tmp;
}
Array.prototype.quick_sort = function(compareFunction) {
function partition(array, compareFunction, begin, end, pivot) {
var piv = array[pivot];
array.swap(pivot, end-1);
var store = begin;
for (var ix = begin; ix < end-1; ++ix) {
if ( compareFunction(array[ix], piv) ) {
array.swap(store, ix);
++store;
}
}
array.swap(end-1, store);
return store;
}
function qsort(array, compareFunction, begin, end) {
if ( end-1 > begin ) {
var pivot = begin + Math.floor(Math.random() * (end-begin));
pivot = partition(array, compareFunction, begin, end, pivot);
qsort(array, compareFunction, begin, pivot);
qsort(array, compareFunction, pivot+1, end);
}
}
if ( compareFunction == null ) {
compareFunction = function(a,b) { return a<=b; };
}
qsort(this, compareFunction, 0, this.length);
}
Update
Peter Michaux pointed out something very important. The sort() function can be made to work if it returns numeric output (-1,0,1). His approach is far superior. Here was a benchmark I took:
var obj_arr1 = [];
var obj_arr2 = [];
var filler = [ { age: 21, name: "Larry" },
{ age: 34, name: "Curly" },
{ age: 10, name: "Moe" } ];
for (var i=0; i<5000; i++) {
rand = Math.floor( Math.random() * 3 );
obj_arr1.push( filler[rand] );
obj_arr2.push( filler[rand] );
}
var s = new Date();
obj_arr1.sort(function(a,b) { return a.name < b.name ? -1 : a.name > b.name ? 1 : 0; });
var e = new Date();
console.log(e.getTime()-s.getTime());
s = new Date();
obj_arr2.quick_sort(function(a,b) { return a.name < b.name });
e = new Date();
console.log(e.getTime()-s.getTime());
That shows drastic differences for arrays as large as 5000 elements (with not too random data). 75 ms versus 4444 ms (over 4 seconds). Doing the math: (4444/75) => 59.253 times better! Moral of the story, don’t rush into thinking something doesn’t exist!
So if that’s the way to do it, then I want to make it easier on me. My arrays are generally going to be under 100 in size, and at such a size building a function dynamically instead of writing a custom function works just about as well (although if you were using objects, polymorphism and a compare function would be the best way to go). Here is a simple function I can use to more quickly build compare functions in order to ascend sort an array on multiple properties!
function buildCompareFunction(arr) {
if (arr && arr.length > 0) {
return function(a,b) {
var asub, bsub, prop;
for (var i=0; i<arr.length; i++) {
prop = arr[i];
asub = a[prop];
bsub = b[prop];
if ( asub < bsub )
return -1;
if ( asub > bsub )
return 1;
}
return 0;
}
} else {
return function(a,b) { return a<=b; };
}
}
Sample usage would be:
var obj_arr = [
{ name: 'Joe', age: 20 },
{ name: 'Joe', age: 10 },
{ name: 'Joe', age: 30 },
{ name: 'Joe', age: 40 },
{ name: 'Joe', age: 20 },
{ name: 'Joe', age: 15 },
{ name: 'Joe', age: 35 },
{ name: 'Joe', age: 25 },
{ name: 'Bill', age: 5 },
{ name: 'Barry', age: 20 },
{ name: 'Paul', age: 20 },
{ name: 'Peter', age: 1 },
{ name: 'Smith', age: 25 },
{ name: 'Kary', age: 30 }
];
obj_arr.sort( buildCompareFunction(['name','age']) );
