Understanding sort() compareFunction

Question

I'm working with an ecommerce platform that lacks the ability to reorder the options of our product attribute fields. It really sucks because to insert a new option you pretty much have to delete all of the existing ones and start over. I'm trying to do it client-side instead. Here's what I'm working with (this one's for a shoe size):

• 9 EE
• 9 1/2 EE
• 10 EE
• 10 1/2 EE
• 11 EE
• 11 1/2 EE
• 9 EEEE
• 9 1/2 D
• 9 1/2 EEEE
• 10 EEEE
• 10 1/2 EEEE
• 11 EEEE
• 9 D
• 11 1/2 EEEE

These are actually the text of some <option>s in a form. The format of the values is X Y Z where:

• X is a whole number
• Y is the string "1/2" and may not be present
• Z is a letter code which is either "D", "E", "EEE", or "EEEE", and may not be present

The desired order of the above would be this:

• 9 D
• 9 1/2 D
• 9 EE
• 9 1/2 EE
• 9 EEEE
• 9 1/2 EEEE
• 10 EE
• 10 1/2 EE
• 10 EEEE
• 10 1/2 EEEE
• 11 EE
• 11 1/2 EE
• 11 EEEE
• 11 1/2 EEEE

I've learned a little bit about javascript's sort() function but haven't been able to fully comprehend how the comparison function that you can pass to it works. I've got this so far:

<select>
    <option>9 EE</option>
    <option>9 1/2 EE</option>
    <option>10 EE</option>
    <option>10 1/2 EE</option>
    <option>11 EE</option>
    <option>11 1/2 EE</option>
    <option>9 EEEE</option>
    <option>9 1/2 D</option>
    <option>9 1/2 EEEE</option>
    <option>10 EEEE</option>
    <option>10 1/2 EEEE</option>
    <option>11 EEEE</option>
    <option>9 D</option>
    <option>11 1/2 EEEE</option>
</select>

I started with the code taken from this answer: https://stackoverflow.com/a/667198/398242

$("select").html($("option").sort(function (a, b) {
    return a.text == b.text ? 0 : a.text < b.text ? -1 : 1
}));

Which sorts the items like this (doesn't work for even the first criteria):

• 10 1/2 EE
• 10 1/2 EEEE
• 10 EE
• 10 EEEE
• 11 1/2 EE
• 11 1/2 EEEE
• 11 EE
• 11 EEEE
• 9 1/2 D
• 9 1/2 EE
• 9 1/2 EEEE
• 9 D
• 9 EE
• 9 EEEE

I see that in javascript '11' > '9' returns false, which in no way makes sense to me.

MDN describes the compare function argument as such, and I kind of get it:

function compare(a, b) {
  if (a is less than b by some ordering criterion)
     return -1;
  if (a is greater than b by the ordering criterion)
     return 1;
  // a must be equal to b
  return 0;
}

...but I haven't got a clue how to adapt this to fit my requirements. I've tried a few things but I just feel like I'm shooting in the dark. I've tried to show that I've taken some time to attempt an understanding of this problem. I'm interested in learning more, but for now I'd just like to get this issue solved.

http://jsfiddle.net/DnwJ6/ Any clues?

Answer 1

Put the values in an array in the order you want them:

var shoeSizes = [ '9 D','9 1/2 D','9 EE','9 1/2 EE', ...]

Use Array.protoype.indexOf (with a shim for older browsers) to get the index of the matched text in the array. Use the index for the value to compare, something like:

function(a,b) {
  return shoeSizes.indexOf(a) - shoeSizes.indexOf(b);
}

If you need to deal with values that aren't in the array, test the value returned by indexOf and substitute a default if it's -1.

Alternatively you can make the sizes the names of property values in an object and assign a specific value:

var shoeSizes = { '9 D': 5, '9 1/2 D': 10, '9 EE': 15, '9 1/2 EE': 20, ...};

Then use the value in the compare:

function(a,b) {
  return shoeSizes[a] - shoeSizes[b];
}

Or to allow for default values:

function(a,b) {
  return (a in shoeSizes? shoeSizes[a] : 1000) - (b in shoeSizes? shoeSizes[b] : 1000);
}

Answer 2

Since you have formatted text, one way is to normalize the text elements before comparing them.

This solution may not be that optimal, but will do the job

$("select").html($("option").sort(function (a, b) {
    return nomalize(a.text) < nomalize(b.text) ? -1 : 1;
}));

function nomalize(val){
    var parts =  val.split(' '), op = '';

    op = parts[0].length == 1 ? '0' + parts[0] : parts[0];
    if(parts.length > 1){
        if(/[a-z]/i.test(parts[1])){
            op += '0/0' + parts[1];
        } else {
            op += parts[1]
        }
    }

    op += parts.length > 2 ? parts[2] : '';
    return op;
}

Demo: Fiddle

If somebody can suggest any solution to optimize it further it will be great

Answer 3

The first thing you have to understand is that 12 is indeed less than 9 if you're sorting the textual items rather than the numbers. That's because <1> <2> is less than <9> <nothing> because 1 and 9 are the "primary keys" in that case.

The second problem you face is whether the length (9 1/2) is the primary key or the width (EE) is. I would suspect the former would make more sense so proceed on that basis.

Having decided that, your best bet is to provide a sort function for the call, one which turns each string into a numeric value and then compares that value. For example:

1. Get the first (space-delimited) field (9) and set your value to that.
2. If the next field exists and is 1/2, add 0.5 to that value.
3. If the last field exists (the alpha one), simply convert that to some value less than 0.5 and add it (eg, a -> 0.01, B -> 0.02, ..., EEEE -> 0.08 and so on).

That last one depends on the relative ordering of widths, I've chosen a typical American system.

What you end up with there is a value which dictates the proper ordering and your sort function can then simply do a numeric comparison. An example follows:

function xlat(s) {
    var s2 = s.split(" ");

    var n = parseInt(s2[0]);
    if (s2.length == 1) { return n; }

    var last = s2[1];
    if (last == '1/2') {
        n = n + 0.5;
        if (s2.length == 2) { return n; }
        last = s2[2];
    }
    var widths = ['A','B','C','D','E','EE','EEE','EEEE','F','G'];
    n = n + widths.indexOf(last) / 100;
    return n;
}

$("select").html($("option").sort(function (a, b) {
    var na = xlat(a.text);
    var nb = xlat(b.text);
    return na == nb ? 0 : na < nb ? -1 : 1;
}));

The xlat functions is the important one here. It first splits the size into an array of 1, 2 or 3 elements and gets the numeric value for the first. If the second and third aren't there, this value gets returned (handles "naked" sizes like 9 or 13).

Otherwise it decides whether it's a half-increment length - this is decided if the second field is 1/2. At this point, it also detects if there is no width and returns the size.

Once past this point, we have the size (either whole or half) and the last variable holds the width. We then simply add a value based on this size's position within an array, suitably modified (divided by 100) so that it doesn't affect the major key.

By using that code with your own, you get (as expected):

9 D
9 EE
9 EEEE
9 1/2 D
9 1/2 EE
9 1/2 EEEE
10 EE
10 EEEE
10 1/2 EE
10 1/2 EEEE
11 EE
11 EEEE
11 1/2 EE
11 1/2 EEEE

Answer 4

You first need to define a proper sort key with which you can make sane comparisons; the following function uses a regular expression to dig out the useful bits of information:

function sortkey(val)
{
    var matches = val.match(/^(\d+)( 1\/2)? (\w+)$/),
    number = +matches[1];

    if (matches[2]) {
      number += 0.5; // add "1/2"
    }

    return [number, matches[3]];
}

The first match is cast into a number; if the second match is available, 0.5 is added. Afterwards, the last match is added as the secondary sort key. The return value is something like this:

[9.5, 'EE']

This structure can then be used for your comparison function:

function compareFunc(a, b) {
    var sa = sortkey(a.text),
    sb = sortkey(b.text);

    if (sa[0] == sb[0]) {
        return sa[1] < sb[1] ? -1 : 1;
    } else {
        return sa[0] < sb[0] ? -1 : 1;
    }
}

Applied to your specific code:

var $sorted = $('select > option').sort(compareFunc);
$('select').html($sorted);

Demo

Answer 5

Check this one out:

$("select").html($("option").sort(function (a, b) {
    var regex = /(\d+)((?: 1\/2)? )([DE]+)/;
    var abreakdown = a.text.match(regex), bbreakdown = b.text.match(regex);
    if (parseInt(abreakdown[1]) === parseInt(bbreakdown[1])) {
        if (abreakdown[3] === bbreakdown[3]) {
            return (abreakdown[2] === bbreakdown[2] ? 0 : (abreakdown[2] < bbreakdown[2] ? -1 : 1));    
        } else {
            return abreakdown[3] < bbreakdown[3] ? -1 : 1;
        }
    } else { return parseInt(abreakdown[1]) - parseInt(bbreakdown[1]); }
}));

It uses a regex to break the pieces down and then do comparison based on each component.

Demo fiddle.

Answer 6

I see you already have a working solution, but just for comparison (pun intended), here is one of the many other ways to do it (fiddle):

// Make a shoe size sortable as text
function sortableSize( text ) {
    // Split the size into parts separated by spaces
    var parts = text.split( ' ' );
    // The first part is the size number;
    // make sure it is two digits (09,10,etc.)
    if( parts[0].length == 1 )
        parts[0] = '0' + parts[0];
    // If it wasn't a 1/2 size, make it 0/2
    if( parts.length == 2 )
        parts.splice( 1, 0, '0/2' );
    // So '9 EE' becomes '09 0/2 EE'
    return parts.join( ' ' );
}

var $options = $('#sizes option');
$options = $options.sort( function( a, b ) {
    a = sortableSize( a.text );
    b = sortableSize( b.text );
    return a < b ? -1 : a > b ? 1 : 0;
});
$('#sizes').html( $options );

This method creates a text representation of each shoe size that is directly sortable as text. Then it sorts using those text representations.