php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #45988 usort assumes comparison operation is transitive
Submitted: 2008-09-03 20:38 UTC Modified: 2008-09-04 17:44 UTC
From: php at sameprecision dot org Assigned:
Status: Not a bug Package: Arrays related
PHP Version: 5.2.6 OS: irrelevant
Private report: No CVE-ID: None
 [2008-09-03 20:38 UTC] php at sameprecision dot org
Description:
------------
Using usort, not all pairs of elements are compared.  If a comparison operation is not transitive, this leads to unexpected ordering, even though every pair of elements are comparable.
This should probably be mentioned in the documentation.


Reproduce code:
---------------
//goal: sort $array so that an element is not a substring of any subsequent elements

$array = array('aa','b','a');

//if $a is a substring of $b, return 1.  Else return -1
function compare($a,$b){
   return strpos($b,$a)===false ? -1 : 1;
}


usort($array,'compare');

print_r($array);

Expected result:
----------------
Array ( [0] => aa [1] => b [2] => a )

Actual result:
--------------
Array ( [0] => a [1] => b [2] => aa )


Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2008-09-04 17:44 UTC] php at sameprecision dot org
I think I have made a mistake in trying to use a generalized sorting algorithm with a comparison operation that is not transitive.
The operation HAS to be transitive or there will always be an example that doesn't work.

sorry!
 
PHP Copyright © 2001-2020 The PHP Group
All rights reserved.
Last updated: Tue Jul 14 14:01:25 2020 UTC