#45988 [Opn->Bgs]: usort assumes comparison operation is transitive

ID: 45988 User updated by: php at sameprecision dot org Reported By: php at sameprecision dot org -Status: Open +Status: Bogus Bug Type: Arrays related Operating System: irrelevant PHP Version: 5.2.6 New Comment: 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! Previous Comments: ------------------------------------------------------------------------ [2008-09-03 20:38:01] 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 ) ------------------------------------------------------------------------ -- Edit this bug report at http://bugs.php.net/?id=45988&edit=1