How does callback ordering work internally?

3

In php, when we want to sort a array in a custom way we can use the function usort .

I know that for this function to work, we should use values 1 , 0 and -1 .

In case, if I wanted to sort this array down in descending order, we could do this:

$array[0]['preco'] = 10.00;
$array[1]['preco'] = 25.00;
$array[2]['preco'] = 20.00;


usort($array, function ($a, $b)
{ 
     return $b['preco'] > $a['preco'] ? 1 : 0;
});

The result would be:

[
     [
       "preco" => 25.0,
     ],
     [
       "preco" => 20.0,
     ],
     [
       "preco" => 10.0,
     ],
   ]
]

If you reverse the variables in the comparison, the result would be different:

  usort($array, function ($a, $b) {
        $a['preco'] > $b['preco'] ? 1 : 0;
  });

The result would be:

[
     [
       "preco" => 10.0,
     ],
     [
       "preco" => 20.0,
     ],
     [
       "preco" => 25.0,
     ],
   ]

I also reduce the comparison by simply doing a subtraction operation, when I want to reverse sort:

   usort($array, function ($a, $b)
   {
       return $b['preco'] - $a['preco'];
   });

I know that if we used the value 0 for all comparisons, the results would remain in the same position.

I know how to change the ordering of values, but I do not understand how php does it internally.

And it is possible to do this operation in Python as well.

Example:

lista = [1, 2, 3]

lista.sort(lambda a,b: b-a)

#[3, 2, 1]

How is this comparison made, so that the languages knew which is the first and which is the second?

What does 1 or -1 internally represent for these sorting functions?

    
asked by anonymous 30.03.2016 / 18:20

1 answer

3

The programmer does not have access to the algorithm that the language uses to sort, and this probably depends on the implementation.

But whatever the ordering algorithm, it works by comparing pairs of elements of the set to be sorted (do not say all works like this, but at least the most well known ones). This is why the callback gets two arguments (a couple of elements) and returns how they compare to each other, being:

  • -1 (or other negative) if a is less than b (i.e., a must be before b ).
  • 0 if the elements are equal or equivalent.
  • 1 (or other positive) if b is less than a (i.e., b must be before a ).

Callback gives you the opportunity to sort by the criteria you want: by an object property, by a composition of values, anything. You decide what comes first in each pair. The language takes this information and puts the set in the order you decided, using a certain algorithm that it implements internally.

I will not go into detail about how well-known sorting algorithms work (they deserve one question each), but the illustrations below clearly show how they work by comparing pairs of elements. Notice the indications in red.

Bubble sort

  

Merge sort

  

Heap sort

  

Quick sort

  

    
30.06.2016 / 23:42