Как работает эта функция?

128

01 января 2021, 02:30

В оф. документации PHP есть пример использования функции sort. Я никак не могу понять по какому принципу сортируются элементы массива. Я понимаю, что делает функция cmp, но не понимаю, что она делает при вызове usort. Т.е. как это работает вообще???

 <?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<br>";
        }
        ?>

Answer 1

я так понимаю, вам не ясно как используется функция обратного вызова применительно к сортировке?
Видимо в целом вам понятно, для чего вообще предназначена функция cmp?

В случае, когда мы используем простые типы данных, например, числа и можем их сравнивать просто так, то функция сравнения нам не требуется. Если же мы сортируем объекты, по какому то полю,или хотим задать какой то определенный алгоритм сравнения, то используем функции сравнения.

Ее задача получив на вход два значения определить какое из них больше и какое меньше, а в результате вернуть сигнал о том, требуется ли поменять эти два значения в массиве местами или нет. На вход поступают не абы какие аргументы, а те, что сравнивает алгоритм самой сортировки, но можно утверждать, что индекс первого элемента всегда меньше индекса второго, или наоборот второго всегда меньше чем первого, то есть не бывает ситуации, что на вход сначала приходит пара с индексами 1,2 а затем 3,2. придет пара 2,3.

function cmp($a, $b){
    return $a - $b;   
}

Что происходит в самой функции сортировки? Вот возьмем самый примитивный пример сортировки методом пузырька:

function bubblesort(&$arr, $cmp){
    $l = count($arr);
    for($i=0; $i < $l; $i++){
        for($j = $i + 1; $j < $l; $j++){
            $swap  = $cmp($arr[$i], $arr[$j]);
            if($swap > 0){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
}

алгоритм беред последовательно пары элементов 0-1, 0-2, 0-3, .. 1-2, 1-3... (двойной цикл) и вызывает вашу функцию cmp для каждой пары. Если возвращается значение 0, то элементы равны и делать ничего не надо. Далее в зависимости от направления сортировки (по возрастанию/убыванию) мы меняем местами элементы.

В данном случае в функцию первым аргументом мы передаем левый, вторым - правый элемент. Возвращает функция разность первого и второго. Значит, если вернулось положительное значение, то левый элемент (с меньшим индексом) больше правого. И если мы сортируем по возрастанию, то нам надо их поменять местами.
Если же вернулось отрицательное, то левый меньше правого, менять для сортировки по возрастанию ничего не требуется.

приведенный метод сортировки имеет довольно низкую эффективность, имеет квадратичную сложность, и, конечно, используется в основном только для решения учебных задач. Под капотом функции usort скрыта одна из функций быстрых сортировок, имеющих сложность n*logn. Но суть использования функции компаратора одинакова везде.