Recipe 6.11 Implementing a Custom Sort

6.11.1 Problem

You want to sort an array in a way such that the basic sort( ) and sortOn( ) methods do not suffice. You want to sort an array in a case-insensitive manner, perform a numeric sort, or use another custom or multikey criterion.

6.11.2 Solution

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

6.11.3 Discussion

If you want complete control over sorting criteria, use the sort( ) method with a custom compare function (also called a sorter function). The compare function is called repeatedly by the sort( ) method to reorder two elements of the array at a time. The compare function receives two parameters (let's call them a and b), which it should compare to determine which one should be ordered first. Your custom compare function should return 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. Your compare function is called 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 do not need to concern yourself with the details of the sorting algorithm; you simply specify the criteria for comparing any two elements.

Here is a simple compare function that performs a case-insensitive sort:

function insensitiveSorter(a, b) {
  itemOne = a.toUpperCase(  );
  itemTwo = b.toUpperCase(  );
  if (itemOne > itemTwo) {
    return 1;
  } else if (itemOne < itemTwo) {
    return -1;
  } else {
    return 0
  }
}

Case-insensitive sorting is useful when you have an array of values with mixed cases, because Flash automatically sorts all uppercase letters before lowercase letters by default:

myArray = ["cardinal", "California", "camel", "Chicago"];
myArray.sort(  );
trace(myArray);  // Displays: California,Chicago,camel,cardinal

However, when you use the case-insensitive sort utilizing the custom sorter function as defined previously, Flash sorts the values in alphabetical order regardless of case:

myArray = ["cardinal", "California", "camel", "Chicago"];
myArray.sort(insensitiveSorter);
trace(myArray);  // Displays: California,camel,cardinal,Chicago

When sorting numbers, the standard sort( ) method produces unexpected results. Numbers are sorted "alphabetically" instead of numerically. After the following example, myArray is [1,12,2,3,4,43], not [1,2,3,4,12,43]:

myArray = [1, 12, 2, 3, 43, 4];
myArray.sort(  )
trace (myArray);  // Displays: 1,12,2,3,4,43 not 1,2,3,4,12,43

Here is a simple compare function that performs a numeric sort, instead of a string-based sort, even if the elements are strings, such as "1", "2", "3":

function numberSorter(a, b) {
  itemOne = parseInt(a);
  itemTwo = parseInt(b);
  if (itemOne > itemTwo) {
    return 1;
  } else if (itemOne < itemTwo) {
    return -1;
  } else {
    return 0
  }
}

You can use it as follows:

myArray = [1, 12, 2, 3, 43, 4];
myArray.sort(numberSorter);
trace (myArray);  // Displays: 1,2,3,4,12,43

In the numberSorter( ) function, the difference between the two numbers yields a positive result if a is greater than b, and a negative result if the opposite is true. It yields 0 if they are equal. Therefore, numeric comparisons of the previous type can be simplified as follows.

function numberSorter(a, b) {
  itemOne = parseInt(a);
  itemTwo = parseInt(b);
  return (itemOne - itemTwo);
}

You can easily modify the sort function to sort the numbers in reverse order, as follows:

function reverseSorter(a, b) {
  itemOne = parseInt(a);
  itemTwo = parseInt(b);
  return (itemTwo - itemOne);
}

Here is a full-fledged example that sorts the cars array by make and year:

// Create an array with elements that have some matching make properties but
// different year and color properties.
cars = new Array(  );
cars.push({make: "Honda",    year: 1997, color: "maroon"});
cars.push({make: "Chrysler", year: 2000, color: "beige"});
cars.push({make: "Mercedes", year: 1985, color: "blue"});
cars.push({make: "Fiat",     year: 1983, color: "gray"});
cars.push({make: "Honda",    year: 1982, color: "white"});
cars.push({make: "Chrysler", year: 1999, color: "green"});
cars.push({make: "Mercedes", year: 2002, color: "tan"});
cars.push({make: "Fiat",     year: 1981, color: "brown"});

// Create the custom compare function. The function is always passed two elements as
// parameters. It is convenient to call them a and b.
function sorter(a, b) {

  // If the make property of a is larger than (meaning it comes alphabetically after)
  // the make property of b, return 1 to sort a after b. If the make property of a is
  // less than the make property of b, then return -1 to sort a before b. Otherwise
  // (if a.make and b.make are the same), perform the comparison on the year
  // property. We use String.toUpperCase(  ) to ensure a case-insensitive comparison.
  // We also convert the year to an integer and use the aforementioned shortcut for
  // numeric comparison.
  makeOne = a.make.toUpperCase(  );
  makeTwo = b.make.toUpperCase(  );
  if (makeOne > makeTwo ) {
    return 1;
  } else if (makeOne < makeTwo) {
    return -1;
  } else {
    return (parseInt(a.year) - parseInt(b.year))
  }
}

// Call the sort(  ) method and pass it a reference to the sorter(  ) compare function.
cars.sort(sorter);

// Loop through the array and output the results.
for (var i = 0; i < cars.length; i++) {
  // Displays the results alphabetically by make, then by year:
  // A green 1999 Chrysler
  // A beige 2000 Chrysler
  // A brown 1981 Fiat
  // A gray 1983 Fiat
  // A white 1982 Honda
  // A maroon 1997 Honda
  // A blue 1985 Mercedes
  // A tan 2002 Mercedes

  trace("A " + cars[i].color + " " + cars[i].year + " " + cars[i].make);
}