Edit report at https://bugs.php.net/bug.php?id=53341&edit=1
ID: 53341
Comment by: cw at clement dot hk
Reported by: goetas at lignano dot it
Summary: Add a stable sorting flag to sort functions (uasort)
Status: Open
Type: Feature/Change Request
Package: Arrays related
Operating System: any
PHP Version: 5.3.3
Block user comment: N
Private report: N
New Comment:
@cmb, this is more like a feature request than a bug report.
Previous Comments:
------------------------------------------------------------------------
[2015-08-13 13:31:12] cmb@php.net
AFAIK PHP 7 uses a stable sort algorithm for small arrays (< 16),
but for larger arrays the algorithm is still not stable.
Furthermore PHP makes no guarantee whether sorting with *sort() is
stable or not.
------------------------------------------------------------------------
[2015-08-13 12:59:01] cw at clement dot hk
Please note that this is fixed since PHP 7, so this issue can be close now.
------------------------------------------------------------------------
[2015-05-08 21:23:05] cmb@php.net
While there might be use cases demanding a stable sort, this is
clearly none of them. Just sort the array with a single usort(),
what is faster, by the way:
<?php
$a = array(
array("l"=>"B", "n"=>2),
array("l"=>"A", "n"=>1),
array("l"=>"C", "n"=>3),
array("l"=>"E", "n"=>5),
array("l"=>"D", "n"=>4),
);
usort($a, function($a1, $a2){ // sort even first
if($a1["n"]%2===0 && $a2["n"]%2!==0){
return -1;
}elseif($a2["n"]%2===0 && $a1["n"]%2!==0){
return 1;
}else{// alpha sort
return strcmp($a1["l"],$a2["l"]);
}
});
print_r($a);
------------------------------------------------------------------------
[2014-03-04 15:43:01] cw at clement dot hk
You can use this before the bug is fixed.
Clement Wong
function stable_uasort(&$array, $cmp_function) {
if(count($array) < 2) {
return;
}
$halfway = count($array) / 2;
$array1 = array_slice($array, 0, $halfway, TRUE);
$array2 = array_slice($array, $halfway, NULL, TRUE);
stable_uasort($array1, $cmp_function);
stable_uasort($array2, $cmp_function);
if(call_user_func($cmp_function, end($array1), reset($array2)) < 1) {
$array = $array1 + $array2;
return;
}
$array = array();
reset($array1);
reset($array2);
while(current($array1) && current($array2)) {
if(call_user_func($cmp_function, current($array1), current($array2)) < 1) {
$array[key($array1)] = current($array1);
next($array1);
} else {
$array[key($array2)] = current($array2);
next($array2);
}
}
while(current($array1)) {
$array[key($array1)] = current($array1);
next($array1);
}
while(current($array2)) {
$array[key($array2)] = current($array2);
next($array2);
}
return;
}
------------------------------------------------------------------------
[2010-11-18 11:11:01] goetas at lignano dot it
Description:
------------
Starting from php 4.1.0 the sorting of arrays is not stable.
With current sort method is not possible to sort two or more times (with different sort functions)
an array with consistent result.
My suggestion is to add a flag to *sort functions to choose the sorting algorithm.
I'm not a c programmer, but i think that can be changed a behavior of zend_qsort with some
parameters or add a mergesort that can be used if stable sort is required.
Test script:
---------------
<?php
$a = array(
array("l"=>"B", "n"=>2),
array("l"=>"A", "n"=>1),
array("l"=>"C", "n"=>3),
array("l"=>"E", "n"=>5),
array("l"=>"D", "n"=>4),
);
usort($a, function($a1, $a2){ // alpha sort
return strcmp($a1["l"],$a2["l"]);
});
usort($a, function($a1, $a2){ // sort odd first
if($a1["n"]%2===0 && $a2["n"]%2!==0){
return -1;
}elseif($a2["n"]%2===0 && $a1["n"]%2!==0){
return 1;
}else{
return 0;
}
});
print_r($a);
Expected result:
----------------
Array
(
[0] => Array
(
[l] => B
[n] => 2
)
[1] => Array
(
[l] => D
[n] => 4
)
[2] => Array
(
[l] => A
[n] => 1
)
[3] => Array
(
[l] => C
[n] => 3
)
[4] => Array
(
[l] => E
[n] => 5
)
)
Actual result:
--------------
Array
(
[0] => Array
(
[l] => D
[n] => 4
)
[1] => Array
(
[l] => B
[n] => 2
)
[2] => Array
(
[l] => E
[n] => 5
)
[3] => Array
(
[l] => C
[n] => 3
)
[4] => Array
(
[l] => A
[n] => 1
)
)
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=53341&edit=1