In php how does usort() function works

Question

I have looked at the php documentation, tutorials online and none of them how usort is actually working. I have an example i was playing with below.

$data = array(

    array('msg' => 'some text','month' => 11,'level' => 10),

    array('msg' => 'some text','month' => 5,'level' => 10),

    array('msg' => 'some text','month' => 8,'level' => 10),

    array('msg' => 'some text','month' => 12,'level' => 10),

    array('msg' => 'some text','month' => 2,'level' => 10),

    array('msg' => 'some text','month' => 3,'level' => 10),

    array('msg' => 'some text','month' => 4,'level' => 10),

    array('msg' => 'some text','month' => 7,'level' => 10),

    array('msg' => 'some text','month' => 10,'level' => 10),

    array('msg' => 'some text','month' => 1,'level' => 10),

    array('msg' => 'some text','month' => 6,'level' => 10),

    array('msg' => 'some text','month' => 9,'level' => 10)

);

I wanted to be able to sort the months from 12 to 1 (since their unorganized) through some help this was the solution

function cmp($a, $b)
{
    if ($a["month"] == $b["month"]) 
    {
       return 0;
    }
    return ($a["month"] < $b["month"]) ? -1 : 1;
}

usort($data, "cmp");

but i dont understand how the function cmp sorts the array. i tried printing out each variable $a and $b like this:

function cmp($a, $b)
{
   echo "a: ".$a['month']."<br/>";
   echo " b: ".$b['month']."<br/>";
   echo "<br/><br/>";
}

and the output was

a: 3
b: 5

a: 9
b: 3

a: 3
b: 8

a: 6
b: 3

a: 3
b: 12

a: 1
b: 3

a: 3
b: 2

a: 10
b: 3

a: 3
b: 11

a: 7
b: 3

a: 4
b: 3

a: 12
b: 2

a: 5
b: 12

a: 12
b: 11

a: 8
b: 12

a: 5
b: 8

a: 2
b: 11

a: 6
b: 9

a: 7
b: 6

a: 6
b: 4

a: 10
b: 6

a: 1
b: 6

a: 9
b: 4

a: 7
b: 1

a: 10
b: 7

it makes no sense to how the sort is working and why cmp($a, $b) is used. i have tried to print out all its processes as you can see but have not come to any solution to how it all works..

thanks

Solution 1

The function cmp itself doesn't do the sorting. It just tells usort if a value is smaller, equal or greater than another value. E.g. if $a = 5 and $b = 9 it will return 1 to indicate that the value in $b is greater than the one in $a.

Sorting is done by usort.

Solution 2

The callback provided to the sorting functions in PHP have three return values:

0:  both elements are the same
-1 (<0): the first element is smaller than the second
1 (>0):  the first element is greater

Now, usort probably uses some kind of quicksort or mergesort internally. For each comparison it calls your callback with two elements and then decides if it needs to swap them or not.

Solution 3

usort() uses an implementation of Quicksort to sort the array, it calls your cmp function as many times as it needs to to fully sort the array using that algorithm.

Solution 4

As the others mentioned, usort uses the Quicksort algorithm. On a side note, you do not need to explicitly do the comparision between two strings. You can use PHP's string compare methods.

The function that you created,

function cmp($a, $b)
{
    if ($a["month"] == $b["month"]) 
    {
       return 0;
    }
    return ($a["month"] < $b["month"]) ? -1 : 1;
}

could simply be written as follows

function compareMyStrings($a, $b){
    return strnatcmp($a["month"], $b["month"]);
}

Hope this helps!

View more solutions

Comments

[Your Common Sense]

your latter function doesn't return anything.

[Corbin]

Are you wanting to know how it all meshes together, or the algorithm usort uses behind the scenes?

[Exploit]

@corbin, yes if its public info.

[Exploit]

@col you need to include the arrays into the test your doing.

[Corbin]

Of course it's public information. You can download the PHP source code after all :). I'm feeling to lazy at the moment to check myself, but I'll trust PaulPRO that it uses a quicksort implementation. For more details than that, read the PHP source code.

[Your Common Sense]

what? what tests? your second cmp function doesn't return anything, means always return 0. running usort with it makes no sense.

[Exploit]

@Col.Shrapnel can you put in a paste all of the code that you are trying so i can tell you what your missing?

[Your Common Sense]

I am talking of YOUR code. Pasted in YOUR question already. Can you see the second variant of the cmp function in your code?

[Exploit]

wow what you said made alot of sense. I should've seen that. do i always have to enter two arguments into the cmp function?

[halfdan]

Yep, the compare function always takes two arguments.

[user1613360]

Usort uses counting sort and not quick sort.Check this ijest.info/docs/IJEST11-03-09-057.pdf.

[Paul]

@user1613360 You've mistaken PHP's usort, for the usort algorithm mentioned in that paper. PHP's usort is implemented with Quicksort.

[aug]

You can find more about PHP sorting here but yes as mentioned by default most sorts in PHP use Quicksort. See the note in the link.

[Sid]

I think it will return -1(not 1 as halfdan mentioned) to indicate that the value in $b is greater than the one in $a.

[mrClean]

+1 This is what I was looking for. In the PHP docs they say PHP versions below 7 have the limits -2147483648 to 2147483647, but they don't clearly lay it out like you did. Your explanation would have made the docs much clearer!