june
1
0
JavaScript Sort an Array of Objects
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:)
// Array of Objects
var obj_arr = age: 21 name: "Larry"
age: 34 name: "Curly"
age: 10 name: "Moe" ;
// This doesn't work!
obj_arrsort function a b return aname < bname; ;
// This does work! (Peter's update, very fast)
obj_arr1sortfunction a b return aname < bname ? -1 :
aname > bname ? 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:
// Defaults to (a<=b) sorting. Great for numbers.
var arr = 123423462123434563213434561234234523425231234345;
// Object Array
var obj_arr = age: 21 name: "Larry"
age: 34 name: "Curly"
age: 10 name: "Moe" ;
arr quick_sort;
// => [23, 345, 1234, 1234, 1234, 2345, 2346, 3456, 3456, 21234, 32134, 42523]
obj_arr quick_sortfunction a b return aname < bname ;
// => Curly, Larry, Moe
obj_arr quick_sortfunction a b return a age < b age ;
// => Moe (10), Larry (21), Curly (34)
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:
var tmp=this a;
this a=this b;
this b=tmp;
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;
if end-1 > begin
var pivot = begin + MathfloorMathrandom * end-begin;
pivot = partition array compareFunction begin end pivot;
qsort array compareFunction begin pivot;
qsort array compareFunction pivot+1 end;
if compareFunction == null
return a<=b; ;
qsortthis compareFunction0thislength;
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 = Mathfloor Mathrandom * 3 ;
obj_arr1push filler rand ;
obj_arr2push filler rand ;
var s = ;
obj_arr1sortfunction a b return aname < bname ? -1 : aname > bname ? 1 : 0; ;
var e = ;
console.log egetTime-sgetTime; // => 75 ms
s = ;
obj_arr2 quick_sortfunction a b return aname < bname ;
e = ;
console.log egetTime-sgetTime; // => 4444 ms
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!
if arr && arrlength > 0
return function a b
var asub bsub prop;
for var i=0; i<arrlength; 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_arrsort buildCompareFunction'name''age';
Peter Michaux on June 15, 2008 at 2:07 am #
JavaScript’s sort works a little differently than you expected
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 ? -1 :
a.name > b.name ? 1 : 0; });