Sorting multi-dim array by multiple values

[bubblenut]

Right, I think this is a tricky one, but then I would say that, I'm the one that's stuck with it 🙂

Here's the array I'm using as a test case. The array is called $test

Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [product_code] => 10448
                    [product_name] => Musicology
                    [artist_name] => PRINCE
                    [price] => 8.99
                )

        [1] => Array
            (
                [product_code] => 9232
                [product_name] => Songs about Jane
                [artist_name] => MAROON 5
                [price] => 8.99
            )

        [2] => Array
            (
                [product_code] => 9205
                [product_name] => Scissor Sisters
                [artist_name] => SCISSOR SISTERS
                [price] => 8.99
            )

        [3] => Array
            (
                [product_code] => 10524
                [product_name] => WESTWOOD: THE JUMP OFF
                [artist_name] => Various
                [price] => 12.99
            )

    )

[1] => Array
    (
        [other_data] => there is different, differently structured data over here which is completely independant
    )

)

Now, looking at the man page for [man]array_multisort[/man] and [man]usort[/man] I found a couple of solutions for ordering by one of the keys (in these example 'price'), here they are below.
array_multisort with temp array

$orderby='price';
foreach($test[0] as $val)
  $sortarray[]=$val[$orderby];
array_multisort($test[0],$sortarray);

usort

$orderby='price';
function opensort($a, $b) {
  global $orderby;
  if(empty($a[$orderby])) return -1;
  if(empty($b[$orderby])) return 1;
  if($a[$orderby]>$b[$orderby]) return 1;
}
usort($test[0],'opensort');

I've even implemented a quicksort for it!

function quicksort(&$arary, $lo, $hi, $column) {
  $i=$lo;
  $j=$hi;
  $x=$array[0][($lo+$hi)/2][$column];

  do {
    while($array[0][$i][$column] > $x) ++$i;
    while($array[0][$j][$column] < $x) --$j;
    if($i<=$j) {
      $h=$array[0][$i];
      $array[0][$i]=$array[0][$j];
      $array[0][$j]=$h;
      $i++; $j--;
    }
  } while($i<=$j);

  if($lo<$j) quicksort($array, $lo, $j, $column);
  if($i<$hi) quicksort($array,$i, $hi, $column);
}
quicksort($test,0,count($test),'price');

All work fine if I only want to order by one key but what I want to achive is a sort similar to MySQL's ORDER BY where I can order by one value and then order by another value within the limits of the first sort. This is doing my head in.

Any ideas?
Thanks
Bubble

[Weedpacket]

Methinks you'll need a stable sort - one that retains the relative order of values that don't actually need to be swapped. Stably sort by the less important field, then by the more important. Merge sort, maybe.

Grunt - it would be nice to pass additional parameters to usort (at least, some method more elegant than a global variable) - pass it an array of field names (in decreasing importance) and then loop through the array, comparing each pair of arguments against each field in turn until they no longer match.

if($a['foo']<$b['foo']) return -1;
if($a['foo']>$b['foo']) return 1;
if($a['bar']<$b['bar']) return -1;
if($a['bar']>$b['bar']) return 1;
....
return 0;

I.e., If the most important field differs, make your decision based on it; otherwise, look at the second most important field, etc.

[bubblenut]

Thanks Weed, I'm going to try it that way as well and then do some profiling. This is the way I came up with (well my boss gave me a nudge in the right direction) using array_multisort, I've got a funny feeling it's going to work out a lot more inefficient than your method

$order=array(array('column'=>'price', 'direction'=>SORT_ASC), array('column'=>'product_code', 'direction'=> SORT_DESC));
$multisort='array_multisort(';
$order_c=count($order);
$test_c=count($res[0]);
for($i=0;$i<$order_c;++$i) {
  for($j=0;$j<$test_c;++$j) {
    $sortarray[$i][$j] = $test[0][$j][$order[$i]['column']];
  }
  $multisort.='$sortarray['.$i.'],'.$column[$i]['direction'].',';
}
$multisort.='$res[0]);';
eval($multisort);

What do you think?
Bubble

[bubblenut]

YAY!!!
<singing>Mine's quicker than Weed's, mine's quicker than Weed's, I beat the genius, I beat the genius</singing>
😃😃😉😃😃

[bubblenut]

I didn't provide the code for my proof

$res=$res2=prodsearch(99,'listid_search',true,true,false,400,false);
echo("<pre>");
print_r($res);
echo("</pre>");


function getTime() {
  list($usec, $sec) = explode(' ',microtime());
  return (float)$usec+(float)$sec;
}

function printArray($array) {
    $array_c=count($array);
    for($i=0;$i<$array_c;++$i) {
        echo($array[$i]['product_code'].' - '.$array[$i]['price'].' - '.$array[$i]['title']."<br />\n");
    }
}

//array_multisort implementation
$column=array(array('column'=>'price', 'direction'=>SORT_ASC), array('column'=>'product_code', 'direction'=> SORT_DESC));
$time_start=getTime();
function opensort(&$res, $column) {
    $multisort='array_multisort(';
    //build the temp arrays
    $res_c=count($res[0]);
    $column_c=count($column);
    for($i=0;$i<$column_c;++$i) {
        for($j=0;$j<$res_c;++$j) {
            $sortarray[$i][$j] = $res[0][$j][$column[$i]['column']];
        }
        $multisort.='$sortarray['.$i.'],'.$column[$i]['direction'].',';
    }
    $multisort.='$res[0]);';
    eval($multisort);
}
opensort($res,$column);
$time_stop=getTime();
printArray($res[0]);
echo("Multisort Method: ".($time_stop-$time_start)."<br />\n<br />\n<br />\n");
//usort implementation
$time_start=getTime();
function uopensort($a, $b) {
    global $column;
    for($i=0;$i<count($column);++$i) {
      if($a[$column[$i]['column']]<$b[$column[$i]['column']]) return $column[$i]['direction'] == SORT_ASC ? -1 : 1;
      if($a[$column[$i]['column']]>$b[$column[$i]['column']]) return $column[$i]['direction'] == SORT_ASC ? 1 : -1;
    }
    return 0;
}
usort($res2[0],'uopensort');
$time_stop=getTime();
printArray($res2[0]);
echo("Usort Method: ".($time_stop-$time_start)."<br />\n");

prodsearch pulls out an array similar in structure to the $test array above.