Mimsy Were the Borogoves

Hacks: Articles about programming in Python, Perl, Swift, BASIC, and whatever else I happen to feel like hacking at.

Stable sorting of numerically indexed arrays in PHP

Jerry Stratton, March 14, 2011

We need to pull news entries out of a database including some items that are sticky and must always be displayed. That’s easy enough to do—just sort by the sticky column first. But we want the sticky items to show up last. Yes, that’s possible to do in MySQL, but it’s going to be a wacky query.

It occurred to me that I could just take the MySQL list, sorted by date with the sticky items first, and then resort it in PHP. I had a vague recollection that sorts in PHP are stable. I went over to usort and found:

4.1.0: A new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal.

Well, crap.

Okay, how hard would it be to take the key into account in a custom sort? If I want it to be generalizable, it probably needs to be a class so that the desired array can be stored as a property; and if I want it to work like the other sort functions, it will need to accept the list by reference and store it by reference.

[toggle code]

  • //for sorting but maintaining original order if the keys are equal.
  • //Example:
  • // $sorter = new StableSorter($myList);
  • // $sorter->addKey('myKey');
  • // $sorter->sort()
  • // $myList is now sorted as it was before, but primarily by ‘myKey’
  • class StableSorter {
    • protected $arrayToSort;
    • protected $sortKeys = array();
    • protected $highKeyIndex;
    • public function __construct(&$array) {
      • $this->arrayToSort = &$array;
    • }
    • public function addKey($key) {
      • $this->sortKeys[] = $key;
    • }
    • public function sort() {
      • $this->highKeyIndex = count($this->sortKeys)-1;
      • uksort($this->arrayToSort, array($this, 'comparison'));
    • }
    • //not really sure why it works as protected
    • protected function comparison($a, $b, $keyIndex = 0) {
      • $aValue = $this->arrayToSort[$a][$this->sortKeys[$keyIndex]];
      • $bValue = $this->arrayToSort[$b][$this->sortKeys[$keyIndex]];
      • if ($aValue === $bValue) {
        • if ($keyIndex < $this->highKeyIndex) {
          • return $this->comparison($a, $b, $keyIndex+1);
        • } else {
          • return $a - $b;
        • }
      • } elseif ($aValue > $bValue) {
        • return 1;
      • } elseif ($aValue < $bValue) {
        • return -1;
      • } else {
        • return 0;
      • }
    • }
  • }

The constructor accepts the array-to-be-sorted by reference; it then stores it as a property by reference, too.

Add keys to sort by, using the addKey() method.

And it calls uksort() via the sort() method.

The comparison method is recursive: so that if there is more than one key to sort by, and the primary key’s values are equal for any two items in the list, it will devolve to the secondary key, and so on.

You can test this with a simple array:

[toggle code]

  • $dragons = array(
    • array('color'=>'green', 'name'=>'Pebbles', 'age'=>'child'),
    • array('color'=>'blue', 'name'=>'Bam-Bam', 'age'=>'child'),
    • array('color'=>'red', 'name'=>'Fred', 'age'=>'adult'),
    • array('color'=>'green', 'name'=>'Barney', 'age'=>'adult'),
    • array('color'=>'blue', 'name'=>'Wilma', 'age'=>'adult'),
    • array('color'=>'red', 'name'=>'Betty', 'age'=>'adult'),
    • array('color'=>'red', 'name'=>'Dino', 'age'=>'adult'),
  • );
  • showDragons('original');
  • $sorter = new StableSorter($dragons);
  • $sorter->addKey('color');
  • //$sorter->addKey('age');
  • //$sorter->addKey('name');
  • $sorter->sort();
  • showDragons('sorted');
  • function showDragons($title='after') {
    • global $dragons;
    • echo strtoupper($title), ":\n";
    • foreach ($dragons as $dragon) {
      • echo "\t", implode(', ', $dragon), "\n";
    • }
  • }

Sorting just by the dragon’s color, you can see that within each color the dragons maintain their previous order. You can uncomment the other two keys to test the recursive sort, and/or to test the stability of the sort.

Start with a clean array!

This class assumes that the numerical keys indexing the array correspond to their value’s position in the list. While it doesn’t require that key 0 be the first item, key 1 the second, and so on, it does require that the second key be greater than the first key, and that the third key be greater than the second key, and so on. If this isn’t true, the class will produce what appear to be strange results, since it uses the key to determine an item’s order in the array, if the values are equal.

PHP appears to have only one type of array, what other programming languages call a dictionary or associative array. Even when you’re using a numerically-indexed array, it’s still just an associative array that uses numbers as its keys. Here’s a simple example:

[toggle code]

  • $items = array();
  • $items[0] = 'zero';
  • $items[1] = 'one';
  • $items[5] = 'five';
  • $items[2] = 'two';
  • foreach ($items as $item) {
    • echo $item, "\n";
  • }

This will print in the same order they’re entered: zero, one, five, and two. The numbers are just keys like any other. Add a “print_r($items)” to the end and you’ll see it:

[toggle code]

  • Array
  • (
    • [0] => zero
    • [1] => one
    • [5] => five
    • [2] => two
  • )

If you need to turn a “dirty” array into a cleanly-ordered one, where the numerical keys match their location in the array, you can use array_values() to reconstruct the list.

A more likely solution

Note that this was mostly just running with an idea. I will probably go with something a lot simpler: loop through and save the sticky items for last. Something like:

[toggle code]

  • $items = $news->make();
  • $stickies = array();
  • foreach ($items as $item) {
    • if ($item['sticky']) {
      • $stickies[] = $item;
    • } else {
      • $this->displayNewsItem($item);
    • }
  • }
  • foreach ($stickies as $item) {
    • $this->displayNewsItem($item);
  • }

As long as I don’t have to pass the array around to other methods expecting it to be in display order, this should work fine. (And, of course, that could also be used to reconstruct an array in the correct order.)

  1. <- readfile and Host
  2. Auto-closing HTML ->