Sorting¶

Given an array of things, it's common to want to sort it in various orders.

Sorting in JavaScript is not quite as easy as it is in Python, but there is a .sort() method on arrays that can be used for sorting.

Let's start with sorting numbers and strings.

Unsurprisingly, strings are sorted in dictionary order, a-z:

words = ['ball','ape','bay','apple'];
words.sort();
console.log(words);
[ 'ape', 'apple', 'ball', 'bay' ]

If you want reverse order, you could sort and then reverse:

words = ['ball','ape','bay','apple'];
words.sort();
words.reverse();
console.log(words);
[ 'bay', 'ball', 'apple', 'ape' ]

But uppercase and lowercase letters don't overlap, so you might not be happy with the following result:

words = ['ball','ape','Boston','Akron'];
words.sort();
console.log(words);
[ 'Akron', 'Boston', 'ape', 'ball' ];

If you want to keep the words the same, but sort them as if they were all the same case, one option is to use a comparison function.

Sorting with a Comparison Function¶

Almost all sorting algorithms in Computer Science are based on pairwise comparison of elements. Any pairwise comparison between two elements, a and b, has three possible outcomes: a<b, a==b, and a>b. The convention in many sorting algorithms is that the comparison function will be invoked on a pair of elements and it has three kinds of return values:

• negative if a<b meaning that a should precede b in sorted order
• zero if a==b meaning that a and b are tied and should be "next to" each other
• positive if a>b meaning that a should follow b in sorted order

That is, if the comparison function returns any negative value, the algorithm will ensure that a comes before b in the sorted array.

The comparison function is supplied as an optional argument to the .sort() method.

Here's one way we could sort strings ignoring case:

function cmp(a,b) {
    var aup = a.toUpperCase();
    var bup = b.toUpperCase();
    if( aup < bup ) {
        return -1;
    } else if ( aup == bup ) {
        return 0;
    } else {
        return 1;
    }
}
words = ['ball','ape','Boston','Akron'];
words.sort(cmp);
console.log(words);
[ 'Akron', 'ape', 'ball', 'Boston' ]

That works, but it's cumbersome. It turns out that there is a built-in string method that compares two strings and returns negative/zero/positive as desired. The name is localeCompare(); the name has locale in it because the method has some features to compare strings in language-specific ways. We might get into this later, but for now we will ignore non-English strings. Thus, we have:

function cmp(a,b) {
    var aup = a.toUpperCase();
    var bup = b.toUpperCase();
    return aup.localeCompare(bup);
}
words = ['ball','ape','Boston','Akron'];
words.sort(cmp);
console.log(words);
[ 'Akron', 'ape', 'ball', 'Boston' ]

Sorting Arrays of Numbers¶

Sorting numbers is surprising:

nums = [1, 3, 2, 11, 33, 22];
nums.sort();
console.log(nums);
[ 1, 11, 2, 22, 3, 33 ]

The reason for this odd result is that the numbers are being sorted as strings. To sort them as numbers, we can again use a comparison function. Since the comparison function needs to return negative if a should come before b, one easy way to do that is to subtract. Here are some examples. I'll use arrow functions for brevity. Here's the basic arrow function I'll use:

(a,b) => a-b

You can try it like this:

cmp = (a,b) => a-b
cmp(10,20);   // -10
cmp(20,10);   // 10

Here are some examples. Copy/paste this code into a JS console to see some results:

cmp = (a,b) => a-b

[1,2].sort(cmp)
[2,1].sort(cmp)

nums = [1, 3, 2, 11, 33, 22];
nums.sort(cmp)
console.log(nums);
[ 1, 2, 3, 11, 22, 33 ]

nums.sort((a,b) => b-a);  // opposite subtraction
console.log(nums);
[ 33, 22, 11, 3, 2, 1 ];

Using subtraction like this helps understand the comparison function and leads to a useful mnemonic:

Mnemonic: the comparison function acts like a-b, if we wanted numbers is ascending order.

Sorting Objects¶

We can use the comparision function to compare complex things such as objects. We'll discuss this more in class, but here's the basic idea:

Sorting Objects¶

When we sort an array of JS objects (dictionaries) we obviously can't subtract them. But the comparison function can access some comparable property of the object and compare the objects using that property.

First, let's create a list of objects:

var x = {name: 'Harry', age: 17};
var y = {name: 'Dumbledore', age: 89};
var z = {name: 'Snape', age: 45};
var cast = [x,y,z];

Now, let's imagine sorting them by age in ascending order. The function needs to reach into each object, pull out the age, and then subtract (just like our earlier comparision functions).

function ageCmp(a, b) {
    return a.age - b.age;
}

Similarly, we can sort by name by reaching into each object, pulling out the name, and then using the localeCompare method:

function nameCmp(a, b) {
    let aname = a.name;
    let bname = b.name;
    return aname.localeCompare(bname);
}

Using these comparison functions, we can sort our cast by age:

cast.sort(ageCmp);
console.log(cast.map((e) => e.age))
cast

resulting in:

And by name:

cast.sort(nameCmp);
console.log(cast.map((e) => e.name));
cast

resulting in:

Summary¶

• sorting requires a comparison function
• the function takes a pair of elements, say a and b and returns:
• negative if a should come before b
• positive if b should come before a
• zero on a tie
• Mnemonic: the comparison function acts like a-b, if we wanted numbers is ascending order.