Cheapest mathmatical mutli-dimensonal array sort cost?

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
darkdss
Forum Newbie
Posts: 11
Joined: Thu Nov 06, 2008 12:40 pm

Cheapest mathmatical mutli-dimensonal array sort cost?

Post by darkdss »

Hi guys, I ran into a problem.
So currently I have an array like this:

Code: Select all

 
$users =    array(array('id'=> 1, 'username' => 'user', 'age' => 42),
        array('id'=> 2, 'username' => 'user', 'age' => 22));

etc.

My goal is to sort this array by age.

Right now I am currently sorting it with array_multisort() which we know is an O(nlogn) algorithm (since all PHP sorting methods are implementations of quicksort).

However before you can use this function I need to run a foreach loop on $users to make an index for the array_multisort() function:

Code: Select all

foreach $users as $key => $row) {
    $user_age[$key]  = $row['age'];
}
 
Running this snip of code gives us a running time O(n).

My question is this. Does this slow down the overall performance? I am shooting for an algorithm that MUST BE an O(nlogn) running time (the worst case O(n^2) from quicksort is ok too) but the current way I have it set up it performs O(nlogn) + O(n).

Any thoughts or how to better approach this?

Thanks for any help :)
darkdss
Forum Newbie
Posts: 11
Joined: Thu Nov 06, 2008 12:40 pm

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Post by darkdss »

Or is it since the overall running time is O(n) + O(n log n) the O(n log n) dominates and the overall running time becomes O(n log n) no matter?
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Post by josh »

darkdss wrote:However before you can use this function I need to run a foreach loop on $users to make an index for the array_multisort() function ... My question is this. Does this slow down the overall performance?
yes
Hannes2k
Forum Contributor
Posts: 102
Joined: Fri Oct 24, 2008 12:22 pm

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Post by Hannes2k »

Hi,
don't worry about the performance. Sorting thousands of items won't be a problem and I guess your $users array doesn't have 10 000 or 100 000 items, or?

But you can also use usort() instead of array_multisort:

Code: Select all

 
//Untested
function ageCmp($a, $b)
{
    return ($a['age'] - $b['age']);
}
 
$users = array(array('id'=> 1, 'username' => 'user', 'age' => 42),
         array('id'=> 2, 'username' => 'user', 'age' => 22)); 
 
usort($users, "ageCmp");
foreach ($users as  $value) {
    echo $value['username'].": ".$value['age']."<br>";
}
 
 
But I don't now if this is faster, so you have to test both solutions.
Post Reply