Sort an array, placing children beneath parents

So I have an array of items in php, some may be linked to others via a parent_id key. I'm looking to sort this array so that any items whose parent is in this array ends up positioned right below the parent.

example: (actual array has many more keys)

some_array[0]['id'] = 15001;
some_array[0]['parent_id'] = 14899;

some_array[1]['id'] = 14723;
some_array[1]['parent_id'] = 0; //parent_id of 0 means item has no parent of its own

some_array[2]['id'] = 14899;
some_array[2]['parent_id'] = 0;

some_array[3]['id'] = 15000;
some_array[3][parent_id'] = 14723;

I'd like to sort these so they end up in this order:

some_array[0]['id'] = 14723;

some_array[1]['id'] = 15000;

some_array[2]['id'] = 14899;

some_array[3]['id'] = 15001;

ie. items are just below their parents.

Thanks in advance!

My shorter version of mattwang's answer:

/**
 * sort parents before children
 *
 * @param array   $objects input objects with attributes 'id' and 'parent'
 * @param array   $result  (optional, reference) internal
 * @param integer $parent  (optional) internal
 * @param integer $depth   (optional) internal
 * @return array           output
 */
function parent_sort(array $objects, array &$result=array(), $parent=0, $depth=0) {
    foreach ($objects as $key => $object) {
        if ($object->parent == $parent) {
            $object->depth = $depth;
            array_push($result, $object);
            unset($objects[$key]);
            parent_sort($objects, $result, $object->id, $depth + 1);
        }
    }
    return $result;
}

Only actual difference is that it sorts an array of objects instead of an array of arrays.

I doubt that you guys are still looking for a real answer to this, but it might help out others with the same problem. Below is a recursive function to resort an array placing children beneath parents.

$initial = array(
    array(
        'name' => 'People',
        'ID' => 2,
        'parent' => 0
        ),
    array(
        'name' => 'Paul',
        'ID' => 4,
        'parent' => 2
        ),
    array(
        'name' => 'Liz',
        'ID' => 5,
        'parent' => 2
        ),
    array(
        'name' => 'Comus',
        'ID' => 6,
        'parent' => 3
        ),
    array(
        'name' => 'Mai',
        'ID' => 7,
        'parent' => 2
        ),
    array(
        'name' => 'Titus',
        'ID' => 8,
        'parent' => 3
        ),
    array(
        'name' => 'Adult',
        'ID' => 9,
        'parent' => 6
        ),
    array(
        'name' => 'Puppy',
        'ID' => 10,
        'parent' => 8
        ),
    array(
        'name' => 'Programmers',
        'ID' => 11,
        'parent' => 4
        )   ,
    array(
        'name' => 'Animals',
        'ID' => 3,
        'parent' => 0
        )                           
    );


/*---------------------------------
function parentChildSort_r
$idField        = The item's ID identifier (required)
$parentField    = The item's parent identifier (required)
$els            = The array (required)
$parentID       = The parent ID for which to sort (internal)
$result     = The result set (internal)
$depth          = The depth (internal)
----------------------------------*/

function parentChildSort_r($idField, $parentField, $els, $parentID = 0, &$result = array(), &$depth = 0){
    foreach ($els as $key => $value):
        if ($value[$parentField] == $parentID){
            $value['depth'] = $depth;
            array_push($result, $value);
            unset($els[$key]);
            $oldParent = $parentID; 
            $parentID = $value[$idField];
            $depth++;
            parentChildSort_r($idField,$parentField, $els, $parentID, $result, $depth);
            $parentID = $oldParent;
            $depth--;
        }
    endforeach;
    return $result;
}

$result = parentChildSort_r('ID','parent',$initial);

print '<pre>';
print_r($result);
print '</pre>';

It's a wind down method that removes elements from the original array and places them into result set in the proper order. I made it somewhat generic for you, so it just needs you to tell it what your 'ID' field and 'parent' fields are called. Top level items are required to have a parent_id (however you name it) of 0.

You can use usort to sort by a user defined function:

function cmp($a, $b)
{
  if ( $a['id'] == $b['id'] ) {
    return 0;

  } else if ( $a['parent_id'] ) {
    if ( $a['parent_id'] == $b['parent_id'] ) {
       return ( $a['id'] < $b['id'] ? -1 : 1 );
    } else {
      return ( $a['parent_id'] >= $b['id'] ? 1 : -1 );
    }
  } else if ( $b['parent_id'] ) {
    return ( $b['parent_id'] >= $a['id'] ? -1 : 1);
  } else {
    return ( $a['id'] < $b['id'] ? -1 : 1 );
  }
}

usort($some_array, "cmp");

Note: this will only work with a tree that is one level deep (meaning no children of children). For more complex trees you probably want to sort the data into a graph and then flatten it.

Edit: fixed to edit a case where $b has a parent but $a does not.

Just use usort() function and compare two different elements of the 'big array' in a way you need. This becomes then a question about 'how do I really decide which element is before which element?'.

The simple usort won't work if you want to support more than one layer of children. There's simply no way to know how two arbitrary elements compare without other information.

I didn't think about it much, so perhaps it doesn't work. But here's a sorting class:

class TopSort
{
  private $sorted, $unsorted;
  private $history;

  public function sort(array $unsorted)
  {
    $this->sorted = array();
    $this->unsorted = $unsorted;
    $this->history = array();

    usort($this->unsorted, function($a, $b)
    {
      return $b['id'] - $a['id'];
    });

    foreach ($this->unsorted as $i => $a)
      if ($a['parent_id'] == 0) $this->visit($i);

    return array_reverse($this->sorted);
  }

  private function visit($i)
  {
    if (!array_key_exists($i, $this->history))
    {
      $this->history[$i] = true;
      foreach ($this->unsorted as $j => $a)
        if ($a['parent_id'] == $this->unsorted[$i]['id']) $this->visit($j);

      $this->sorted[] = $this->unsorted[$i];
    }
  }
}

$sorter = new TopSort();
$some_array = $sorter->sort($some_array);

The idea here is to first sort in reverse by id. Then build up a new array by inserting the deepest elements (those with no children) first. Since we initially sorted the array by reverse id, it should mean the entire thing is upside down. After reversing the array, it should be exactly like you want. (Of course one could unshift items onto the array to avoid the reverse operation, but that might be slower...)

And this is very unoptimized as it iterates over the entire array many, many times. With a little rework, it wouldn't need to do that.

Here's an alternative class that is more optimized:

class TopSort
{
  private $sorted;

  public function sort(array $nodes)
  {
    $this->sorted = array();

    # sort by id
    usort($nodes, function($a, $b) {
      return $a['id'] - $b['id'];
    });

    # build tree
    $p = array(0 => array());
    foreach($nodes as $n)
    {
      $pid = $n['parent_id'];
      $id = $n['id'];

      if (!isset($p[$pid]))
        $p[$pid] = array('child' => array());

      if (isset($p[$id]))
        $child = &$p[$id]['child'];
      else
        $child = array();

          $p[$id] = $n;
      $p[$id]['child'] = &$child;
      unset($child);

      $p[$pid]['child'][] = &$p[$id];    
    }
    $nodes = $p['0']['child'];
    unset($p);

    # flatten array
    foreach ($nodes as $node)
      $this->flatten($node);

    return $this->sorted;
  }

  private function flatten(array $node)
  {
    $children = $node['child'];
    unset($node['child']);
    $this->sorted[] = $node;
    foreach ($children as $node)
      $this->flatten($node);
  }
}

$sorter = new TopSort();
$sorted = $sorter->sort($some_array);

It's a three step approach:

1. Sort by id (usort)
2. Build nested array structure.
3. Flatten array in pre-order.

By virtue of presorting by id, each group of children should be sorted correctly.