How to understand usort logic?

Question

I'm trying to understand how php function usort works. I have such code:

<?php 
$users[] = array('login' => 'moon', 'name' => 'Chris');
$users[] = array('login' => 'star', 'name' => 'Piter');
$users[] = array('login' => 'mars', 'name' => 'Tim');
$users[] = array('login' => 'earth', 'name' => 'Garry');

function compare($a, $b) {                  
    echo $a['login'] . '--' . $b['login'] . '<br />';
    echo strcmp($a['login'], $b['login']) . '<br />';
    return strcmp($a['login'], $b['login']);              
}
usort($users, "compare");

echo '<pre>'; print_r($users); echo '</pre>';
?>

It will output such result:

star--moon
1
star--mars
1
earth--star
-1
moon--earth
1
mars--moon
-1
earth--mars
-1
Array
(
    [0] => Array
        (
            [login] => earth
            [name] => Garry
        )

    [1] => Array
        (
            [login] => mars
            [name] => Tim
        )

    [2] => Array
        (
            [login] => moon
            [name] => Chris
        )

    [3] => Array
        (
            [login] => star
            [name] => Piter
        )

)

As far as I understand second param should be comparison function and it can only return 3 values (-1,0,1) and usort use this results to sort array? Also I read, usort use Quicksort implementation to sort array. That is why star is first and moon - second? Quicksort divide array into two parts and then sort it? And can I implement this function for 2,3 dimensions array?

score 2 · Accepted Answer · edited May 23 '17 at 12:24

2

Yes, usort uses the comparison function, to compare the values and sort the array with the quicksort algorithm. From http://php.net/manual/en/function.usort.php:

The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

Links to the implementation of usort in PHP can be found here: What sort algorithm does PHP use?. According to http://murilo.wordpress.com/2011/02/05/phps-sort-functions-are-bad-designed/ the algorithm uses the middle element as the pivot element, implemented as this:

offset = (end - begin) >> 1;

This should be why the algorithm uses 'star' as the first pivot element.

For multidimensional arrays, use uasort if you want to maintain index association. This question contains an example of sorting multidimensional arrays.

edited May 23 '17 at 12:24

Community

1
1

answered Jun 30 '12 at 10:45

Fredrik Rafn Strandberg

159
13

Great answer. But can you explain one moment. In the article at your answer written that better to use `shuffle` before sorting. This `shuffle` has no influence on pivot element? It's algorithm feature that it better work with shuffled arrays? – Viacheslav Kondratiuk Jun 30 '12 at 14:18
Yes, shuffling the array before sorting may avoid worst-case scenarios, like when the array is already sorted, but the algorithm still picks the middle element as the pivot element. But this middle element is probably a different element after shuffling the array, than before shuffling. – Fredrik Rafn Strandberg Jun 30 '12 at 15:34

score 1 · Answer 2 · answered Jun 29 '12 at 19:47

1

You're telling usort which item to place first when it compares any two items in your array. Your function is returning the strcmp comparison of the login values of the elements, so it's putting all of your elements in alphabetical order based on the login name.

answered Jun 29 '12 at 19:47

Christopher Armstrong

7,907
2
26
28

And how it decide what elements it should compare during next iteration? And, also, it should compare every element each other? – Viacheslav Kondratiuk Jun 29 '12 at 19:58
Read the comments on http://php.net/manual/en/function.usort.php - specifically the first one. It doesn't compare every element with every other element - the sorting algorithm doesn't need to. – Christopher Armstrong Jun 29 '12 at 20:04

How to understand usort logic?

2 Answers2

Linked