How does usort work?

PHP
1

I’m trying to understand how usort works. So I used this code:

<?php
function usort_cmp($a, $b) {
echo $a . "->" . $b . "<br />\
";

}

$arr = array(1,2,3,4);
usort($arr, "usort_cmp");

?>

Which results in the following output:
2->1
4->2
3->2
4->3

But I can’t understand why this output is like it is?
I’ve read that usort uses the bubblesort methode. Looked on wikipedia how that worked. So I expected it to loop through the array as follows:

compare 1 with 2 (switch if necessary)
compare 2 with 3 (switch if necessary)
compare 3 with 4 (switch if necessary)
compare 1 with 2 (switch if necessary)
compare 2 with 3 (switch if necessary)
compare 1 with 2 (switch if necessary)

Can someone explain to me why usort outputs this random looking comparison (though not really random cause it is the same every time I run the script).

2

I think you are mixing some things…

from the manual:

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.

location: http://php.net/manual/en/function.usort.php

your comparison function doesn’t return anything, it just echos out stuff… there is no logic in there.
usort doesn’t use the bubble comparsion at all, the comparison depends on what you define in the comp_func parameter.

3

Well, I was echoing stuff, because I wanted to know what $a was and what $b. I know it should return 1, 0 or -1 , but I can’t understand why the order of each comparison is like it is shown in the output

This is the sample from the manual:

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

$a = array(3, 2, 5, 6, 1);

usort($a, "cmp");

foreach ($a as $key => $value) {
    echo "$key: $value\
";
}
?>

So the echoes from my own script tell me that it first compares 2 ($a) with 1 ($b), then it compares again $a being 4 and $b being 2, then 3 with 2 then 4 with 3. But I can’t understand why each time it compares the same numbers in the same order? There must be some algorithm here, but which one?

4

Pretty sure it’s quicksort, not bubble sort, which explains the order of comparisons.

5

Well it’s difficult to back-engineer the algorithm behind it…
from the manual:

Note: If two members compare as equal, their order in the sorted array is undefined.

This means it is not a stable sorting… so that rules out bubblesort, which is stable.
on Wikipedia there is a list od algoritmes:

so it could be one of those unstable ones, or even a custom one from Zend…

I’m not even sure if it is quicksort… because quicsort takes a pivot element, then makes two lists bigger and smaller and then applies the sorting again to those 2 lists…

In the test I did, I became this:

3 -> 2
3 -> 1
3 -> 4
6 -> 3
5 -> 3
4 -> 3
2 -> 1
5 -> 4
6 -> 5

So we would asume that 3 is the pivot element…
2,1 are in the lesser list, 4,5,6 in the greater
but then he compares 4 to 3 again… which doesn’t make sence in the quicksort

6

From the PHP source code that will probably make zero sense…
zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_user_compare, 1 TSRMLS_CC)

array.c


/* {{{ proto bool usort(array array_arg, string cmp_function)
   Sort an array by values using a user-defined comparison function */
PHP_FUNCTION(usort)
{
    zval *array;
    int refcount;
    PHP_ARRAY_CMP_FUNC_VARS;

    PHP_ARRAY_CMP_FUNC_BACKUP();

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "af", &array, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
        PHP_ARRAY_CMP_FUNC_RESTORE();
        return;
    }

    /* Clear the is_ref flag, so the attemts to modify the array in user
     * comaprison function will create a copy of array and won't affect the
     * original array. The fact of modification is detected using refcount
     * comparison. The result of sorting in such case is undefined and the
     * function returns FALSE.
     */
    Z_UNSET_ISREF_P(array);
    refcount = Z_REFCOUNT_P(array);

    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_user_compare, 1 TSRMLS_CC) == FAILURE) {
        RETVAL_FALSE;
    } else {
        if (refcount > Z_REFCOUNT_P(array)) {
            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Array was modified by the user comparison function");
            RETVAL_FALSE;
        } else {
            RETVAL_TRUE;
        }
    }
    
    if (Z_REFCOUNT_P(array) > 1) {
        Z_SET_ISREF_P(array);
    }

    PHP_ARRAY_CMP_FUNC_RESTORE();
}
/* }}} */

zend_hash.c


ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
                            compare_func_t compar, int renumber TSRMLS_DC)
{
    Bucket **arTmp;
    Bucket *p;
    int i, j;

    IS_CONSISTENT(ht);

    if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
        return SUCCESS;
    }
    arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
    if (!arTmp) {
        return FAILURE;
    }
    p = ht->pListHead;
    i = 0;
    while (p) {
        arTmp[i] = p;
        p = p->pListNext;
        i++;
    }

    (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);

    HANDLE_BLOCK_INTERRUPTIONS();
    ht->pListHead = arTmp[0];
    ht->pListTail = NULL;
    ht->pInternalPointer = ht->pListHead;

    arTmp[0]->pListLast = NULL;
    if (i > 1) {
        arTmp[0]->pListNext = arTmp[1];
        for (j = 1; j < i-1; j++) {
            arTmp[j]->pListLast = arTmp[j-1];
            arTmp[j]->pListNext = arTmp[j+1];
        }
        arTmp[j]->pListLast = arTmp[j-1];
        arTmp[j]->pListNext = NULL;
    } else {
        arTmp[0]->pListNext = NULL;
    }
    ht->pListTail = arTmp[i-1];

    pefree(arTmp, ht->persistent);
    HANDLE_UNBLOCK_INTERRUPTIONS();

    if (renumber) {
        p = ht->pListHead;
        i=0;
        while (p != NULL) {
            p->nKeyLength = 0;
            p->h = i++;
            p = p->pListNext;
        }
        ht->nNextFreeElement = i;
        zend_hash_rehash(ht);
    }
    return SUCCESS;
}
7

Yes, it’s quicksort.
http://svn.php.net/viewvc/php/php-src/branches/PHP_5_3/Zend/zend_qsort.c?revision=293155&view=markup