Sorting out JavaScript Array Sorting

Tweet

Consider the following JavaScript code:

var a = [30,2,1,9,15];a.sort();alert(a);

What would be output?If you’re expecting 1,2,9,15,30, you’ll be surprised to hear the actual result is 1,15,2,30,9. Don’t give up on JavaScript just yet; array sorting is incredibly powerful once you know how to use it.So what’s going on? When nothing is passed to the sort method, every value is converted to a string and sorted in lexicographic order, i.e. “15” will come before “2”. So will “10” and “19999999”.To fix the problem, we need to pass a comparison function to the sort() method. The function must take 2 parameters — we’ll name them a and b — and return:

  • a value less than zero if a is less than b
  • a value greater than zero if a is greater than b
  • zero if a and b are equal

The simplest numeric compare function is therefore:

function compare(a, b) {	return a - b;}

We can pass the compare function as as argument for the sort method or write it inline, e.g.

var a = [30,2,1,9,15];a.sort(function(a,b) { return a-b; });alert(a);

The output is now a far more logical 1,2,9,15,30.One of the great things about JavaScript is that our comparison functions can sort any type of object by any property. For example, we’ll define a list of locations and home co-ordinates:

// location co-ordinatesvar locations = [	{ name: "shops", x:3, y:4 },	{ name: "library", x:5, y:3 },	{ name: "pub", x:1, y:2 }];// home co-ordinatesvar home = { name: "home", x:0, y:0 };

Next, we’ll add a little Pythagoras to a function which calculates the distance between two points:

// distance between 2 co-ordinatesfunction distance(p1, p2) {	return Math.sqrt(Math.pow(p1.x-p2.x,2)+Math.pow(p1.y-p2.y,2));}

We can now sort the locations by distance from home — shortest to the furthest trip:

// sort by shortest distance homelocations.sort(	function(a, b) {		return distance(home,a)-distance(home,b);	});// locations sorted: pub, shops, library

Or we could sort by furthest to shortest distance by reversing the parameters:

// sort by furthest distance homelocations.sort(	function(b, a) {		return distance(home,a)-distance(home,b);	});// locations sorted: library, shops, pub

Or we can order location names alphabetically:

locations.sort(	function(a, b) {		if (a.name < b.name) return -1;		if (a.name > b.name) return 1;		return 0;	});// locations sorted: library, pub, shops

It’s easy to develop a range of reusable sorting functions which can be applied to any object containing similar property names. In that respect, JavaScript sorting is easier and more flexible than many other languages.

note:Want more?

If you want to read more from Craig, subscribe to our weekly tech geek newsletter, Tech Times.

Free book: Jump Start HTML5 Basics

Grab a free copy of one our latest ebooks! Packed with hints and tips on HTML5's most powerful new features.

  • Tim

    “In that respect, JavaScript sorting is easier and more flexible than many other languages”

    That said, languages like PHP are smart enough to guess what algorithm to apply based on the data types being fed into it. An array of numbers will be sorted numerically by default, and a array of strings sorted lexicographically.

    Considering Javascript is type aware, it should be able to figure that out too.

    I was under the impression that most languages have a sort function that allows the passing of a custom sort function. eg. usort in PHP

    Some examples I found with a quick search online:

    http://au.php.net/manual/en/function.usort.php

    http://msdn.microsoft.com/en-us/library/system.windows.forms.listbox.sort.aspx

    http://www.csharpfriends.com/Articles/getArticle.aspx?articleID=377

    • MisterMutation

      Tim,
      I respectfully disagree that this is the “smart” thing to do.
      I think it’s better that sort has a specific well-defined behavior. I always know what calling sort on an array in JS will do.
      If I need a different behavior, it’s trivial to implement and it will probably make my intentions more explicit.
      As it is now, any time I see
      bar.sort();
      I know exactly what’s going on…for *any* value of bar[...].
      If I see:
      bar.sort(numeric);
      I know that the standard functionality is being modified.
      If we follow PHP’s lead
      foo.sort();
      is unclear.
      Not to mention what happens if the array is comprised of mixed types.

  • Kevin Albs

    Thats pretty cool, I never knew Javascript sorted arrays like that (although I guess I don’t use Javascript arrays too often). I’m sure I’ll find some use for the resuable sorting functions. Thanks.

  • http://codefisher.org/ codefisher

    Every programming language I have used had a way to sort with both a custom defined function and without. The only difference is that the default one worked 90% of the time.

  • Jos Hirth

    There is no need to use Math.sqrt if you want to sort by distance. For sorting it doesn’t matter if all distances are squared.

    Same thing goes for circle/circle collision detection for example. You only need to know if the squared distance is smaller than the sum of the radii squared; the actual distance isn’t of any interest, which means the expensive sqrt call can be avoided.

    • http://www.optimalworks.net/ Craig Buckler

      Good point Jos although, in this case, I’ve created a distance() function which could be used elsewhere. If Math.sqrt isn’t used, you should probably rename the function or make it private.

      • Jos Hirth

        I also wouldn’t use Math.pow for this [I didn't actually read the code earlier, I just looked for sqrt], since calling functions is always a bit expensive. In theory a JS engine could optimize this special case and inline the computation right away, but I doubt that there is any engine which does that kind of thing.

        Math.pow(p1.x-p2.x,2)+Math.pow(p1.y-p2.y,2)

        is the same as:

        (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)

        Speaking of special cases, since we compare the distances of those points relative to one specific point which happens to lie on the origin, we can simplify the calculations even further.

        locations.sort(
        function(a, b) {
        return (a.x+a.y)*(a.x+a.y) – (b.x+b.y)*(b.x+b.y);
        }
        );

        That’s 8 function calls less per comparison.

        Surprisingly, this still isn’t the optimal solution. The distances are calculated each time you compare two objects and sorting isn’t linear (it’s typically O(n log n) to O(n²)).

        You can cheat around that by augmenting those objects with an extra property which stores that value you want to use for comparison. This way the calculations only need to be performed once.

        So, if you have many items and a computationally expensive comparison function, you might want to give that approach a try.

  • Anonymous

    My only complaint is that you listed “pub” last.

    • http://www.optimalworks.net/ Craig Buckler

      But did you notice that the pub was the closest to home? That’s the way it should be!

  • http://icoland.com/ glenngould

    I’d like to share two custom sort functions I’ve coded.
    First one is to randomly sort the array (shuffle):
    //———————————-
    function sortRandom(a,b) {
    return 0.5 – Math.random();
    }
    //———————————-
    I needed to sort a set of letters, which might contain Turkish specific characters or a “?” (joker letter), in a Facebook application. I don’t remember if there is a simpler way to do it, but any way here is my solution with a custom sort function:
    //———————————-
    function sortTR(a,b){
    switch (a) {
    case ‘Ç': a=’CA'; break;
    case ‘Ğ': a=’GA'; break;
    case ‘İ': a=’IA'; break;
    case ‘Ö': a=’OA'; break;
    case ‘Ş': a=’SA'; break;
    case ‘Ü': a=’UA'; break;
    case ‘?': a=’ZA'; break;

    }
    switch (b) {
    case ‘Ç': b=’CA'; break;
    case ‘Ğ': b=’GA'; break;
    case ‘İ': b=’IA'; break;
    case ‘Ö': b=’OA'; break;
    case ‘Ş': b=’SA'; break;
    case ‘Ü': b=’UA'; break;
    case ‘?': b=’ZA'; break;
    }

    if (a>b)
    return 1;
    if (a==b)
    return 0;
    if (a<b)
    return -1;
    }
    //———————————-

  • c_spha

    I would like to request a lot more blogs on JavaScript in future. thanks