Req #53341 [Opn]: Add a stable sorting flag to sort functions (uasort)
| From: | cmb@php.net | Date: | Fri, 08 May 2015 21:23:08 +0000 |
| Subject: | Req #53341 [Opn]: Add a stable sorting flag to sort functions (uasort) | ||
| References: | 1 | Groups: | php.bugs |
| Request: | Send a blank email to php-bugs+get-192592@lists.php.net to get a copy of this message | ||
Edit report at https://bugs.php.net/bug.php?id=53341&edit=1
ID: 53341
Updated by: cmb@php.net
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:
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);
Previous Comments:
------------------------------------------------------------------------
[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