Recipe 5.11. Implementing a Custom Sort

Problem

You want to sort an array using more complex logic than an alphabetical or numeric sort.

Solution

Use the sort( ) method and pass it a reference to a compare function.

Discussion

If you want complete control over sorting criteria, use the sort( ) method with a custom compare function (also called a sorter function). The sort( ) method repeatedly calls the compare function to reorder two elements of an array at a time. It sends the compare function two parameters (let's call them a and b). The compare function then determines which one should be ordered first by returning a positive number, a negative number, or 0, depending on how the elements are to be sorted. If the function returns a negative number, a is ordered before b. If the function returns 0, then the current order is preserved. If the function returns a positive number, a is ordered after b. The sort( ) method calls the compare function with every relevant combination of elements until the entire array has been properly ordered. Using a custom compare function is easier than it sounds. You don't need to concern yourself with the details of sorting the entire array; you simply specify the criteria for comparing any two elements.

One example of when you would want to use a custom sorter is when you need to sort a list of strings, but you need to process the strings somehow before sorting them. Say you are building a music program that needs to display a list of bands. If you just sorted the bands alphabetically, all the bands whose names began with "The" would appear together in the T section, which is probably not what you want. You can define a compare function that strips off "The" from the beginning of the name before comparing the bands. Here is the code to set up the array, perform a simple sort, and display the results:

var bands:Array = ["The Clash",
                   "The Who",
                   "Led Zeppelin",
                   "The Beatles",
                   "Aerosmith",
                   "Cream"];
bands.sort(  );
for(var i:int = 0; i < bands.length; i++) {
    trace(bands[i]);

    /* output:
       Aerosmith
       Cream
       Led Zeppelin
       The Beatles
       The Clash
       The Who
    */
}

To handle this, call the sort( ) method passing the bandNameSort compare function:

var bands:Array = ["The Clash",
                   "The Who",
                   "Led Zeppelin",
                   "The Beatles",
                   "Aerosmith",
                   "Cream"];
bands.sort(bandNameSort);
for(var i:int = 0; i < bands.length; i++) {
    trace(bands[i]);
    /* output:
       Aerosmith
       The Beatles
       The Clash
       Cream
       Led Zeppelin
       The Who
    */
}

function bandNameSort(band1:String, band2:String):int
{
    band1 = band1.toLowerCase(  );
    band2 = band2.toLowerCase(  );
    if(band1.substr(0, 4) == "the ") {
        band1 = band1.substr(4);
    }
    if(band2.substr(0, 4) == "the ") {
        band2 = band2.substr(4);
    }
    if(band1 < band2) {
        return -1;
    }
    else {
        return 1;
    }
}

The bandNameSort( ) function first converts both band names to lowercase, ensuring a case-insensitive sort. Then it checks to see if either band name begins with "The ". If so, it grabs the portion of the string from the fourth character to the end, which is everything after the word "The" plus the space.

Finally, it compares the two processed strings, returning -1 if the first string should go first, and 1 if the first string should go second. As you can see, the output is more in line with what you would expect.

There is no limit to how complex the compare function can be. If you are sorting a list of objects, you can build in logic that reads multiple properties of each object, performs calculations on their data, compares them, and returns the results.

Realize that the compare function may be run hundreds or even thousands of times in a single sort of a large array, so be careful about making it too complex.