PHP usort () order in case of equality

Question

The PHP manual for usort () says:

If two members are compared as equal, their relative order in the sorted array is not defined.

Also,

A new sorting algorithm was introduced. The cmp_function function does not preserve the original order in which elements are compared as equal.

Then my question is: what happens if the two elements are equal (for example, a user-defined function returns 0)? I use this function, and obviously equal elements are randomly located in the sorted array.

Answer 1

Be careful not to confuse "undefined" and "random".

It is assumed that a random implementation will give different orders each time. This would mean that there is some code to shuffle the results when they are considered equal. This will make the algorithm more complex and slow, and will rarely be the desired result.

What undefined means is the opposite: when designing an algorithm, there is absolutely no need to exercise caution in order to have a predictable or stable order. This means that the result may be different each time it is run, if this is a side effect of the algorithm for this data.

You can see the implementation of kernel sorting in the PHP source code . It consists of a mixture of "quick sort" (divide and conquer) and insertion sort (a simpler algorithm that works on short lists) with manually optimized routines for lists of 2, 3, 4 and 5 elements.

Thus, the exact behavior of equal members will depend on factors such as the size of the list, where equal members are on the list, how many equal members are in the same batch, etc. In some situations, the algorithm will see that they are identical, and not replace them (ideal, because replacing takes time); in others, he will not directly compare them until they are already moved relative to other things, so they will be in a different order.

Answer 2

I also found the same thing as sorting my array , then I found some kind of user-executed function, because php has some restriction on the use of a specific sorting function.

http://php.net/manual/en/function.uasort.php#Vd114535

PHP 7 uses a stable sorting algorithm for small arrays (<16), but for large arrays the algorithm is still unstable. Furthermore, PHP does not guarantee whether sorting with * sort () will be stable or not https://bugs.php.net/bug.php?id=53341 .

Answer 3

If I have an array from ['b', 'a', 'c', 'b'] , and I would have to sort it, I would get: ['a','b','b','c'] . Since 'b' == 'b' php cannot guarantee that someone comes before another, so the sort order is undefined ', however, since they are equal, does it matter?

If you use a sort function that returns 0 for unequal objects, you run into another problem altogether.

Answer 4

I also ran into the same problem when 2 rows have the same values, and when the sort function is applied, its order changes, which I did not want. I want to sort the keys based on their values, if they are equal, do not change the order. So here is my solution-

 // sample array $arr = Array("a" => 0.57,"b" => 1.19,"c" => 0.57,"d" => 0.57,"e" => 0.57,"f" => 0.57,"g" => 0.57,"h" => 0.57,"i" => 0.99,"j" => 1.19,"k" => 1.19); $multi_arr = []; foreach ($arr as $k=>$val){ $multi_arr["$val"][] = array($k=>$val); } uksort($multi_arr, function ($a, $b) { return $b > $a ? 1 : -1; }); $s_arr = []; foreach ($multi_arr as $k=>$val){ foreach($val as $p_id){ $p_arr = array_keys($p_id); $s_arr[] = $p_arr[0]; } } print_r($s_arr); 

output-

Array ([0] => b, [1] => j, [2] => k, [3] => i, [4] => a, [5] => c, [6] => d , [7] => e, [8] => f, [9] => g, [10] => h)

Answer 5

understand that php doesn't care about the order if all the compared values ​​are the same.

Example:

$temp=array("b"=>"10","c"=>"10","d"=>"10","e"=>"4");

as indicated above, the array has 4 array lengths, in which 3 have the same values ​​as shown b, c, d = 10; arsort() // The arsort () function sorts the associative array in descending order, according to the value

if print_r(arsort($temp)) o / p: => Array ( [b] => 10 [c] => 10 [d] => 10 [e] => 4 )

this means that it returns an array after sorting the equal value, but keeps the position (order) the same for equal values

but

if $temp=array("a"=>"4",b"=>"10","c"=>"10","d"=>"10","e"=>"4"); here in the above array, b, c, d = 10 are limited by two extreme left and right arrays having a value less than the center values ​​(b, c, d = 10)

arsort above temp - o / p: Array ( [c] => 10 [b] => 10 [d] => 10 [a] => 4 [e] => 4 )

it gives the middle part ie [c] the array in the center. this means that if identical values ​​or equal value arrays are bounded on both sides by an array with lower values, and the first value is lower, then the order of equal gives the average of the three values ​​of the array as the first in these three.