There is no spoon
Difference between revisions of "UE3 talk:Insertion Sort Macro"
m |
m (→Possible Optimization: should be correct in most cases, yes) |
||
| Line 2: | Line 2: | ||
Right now within the inner loop it compares the two elements 3 times. A == B, A > B, B > A. But general rules dictate, that if !(A > B), and !(B > A) then it must be A == B, right? (As also explained in the document). So the first compare is actually not needed, thus reducing the requirement for a additional operator to implement for custom types. Is my assumption correct? --[[User:Elmuerte|elmuerte]] 19:49, 16 September 2009 (UTC) | Right now within the inner loop it compares the two elements 3 times. A == B, A > B, B > A. But general rules dictate, that if !(A > B), and !(B > A) then it must be A == B, right? (As also explained in the document). So the first compare is actually not needed, thus reducing the requirement for a additional operator to implement for custom types. Is my assumption correct? --[[User:Elmuerte|elmuerte]] 19:49, 16 September 2009 (UTC) | ||
| + | |||
| + | Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the ''else'', or == right at the beginning and only either < or >, handling the other in the ''else''. Only float NaN values might break things as NaN <=> X is always ''false'', even if X also is NaN. —[[User:Wormbo|Wormbo]] 05:47, 17 September 2009 (UTC) | ||
Revision as of 22:47, 16 September 2009
Possible Optimization
Right now within the inner loop it compares the two elements 3 times. A == B, A > B, B > A. But general rules dictate, that if !(A > B), and !(B > A) then it must be A == B, right? (As also explained in the document). So the first compare is actually not needed, thus reducing the requirement for a additional operator to implement for custom types. Is my assumption correct? --elmuerte 19:49, 16 September 2009 (UTC)
Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the else, or == right at the beginning and only either < or >, handling the other in the else. Only float NaN values might break things as NaN <=> X is always false, even if X also is NaN. —Wormbo 05:47, 17 September 2009 (UTC)
