Always snap to grid
Difference between revisions of "UE3 talk:Insertion Sort Macro"
m (→Possible Optimization: should be correct in most cases, yes) |
m (→Possible Optimization: maybe use array.InsertItem(index,value)) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 4: | Line 4: | ||
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) | 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) | ||
| + | |||
| + | I've changed the algorithm to not use the equals operator, if !(A > B || B > A) then it doesn't really matter which one comes first, so it shouldn't affect sorting much anyway. Also, the new code makes the operator usage a parameter so you can now easily change the operator used and perform reverse sorting. --[[User:Elmuerte|elmuerte]] 18:42, 17 September 2009 (UTC) | ||
| + | |||
| + | Instead of using array.Insert(index, 1) and array[index] = value, array.InsertItem(index, value) might be a bit more efficient. —[[User:Wormbo|Wormbo]] 16:51, 26 September 2009 (UTC) | ||
Latest revision as of 09:51, 26 September 2009
Possible Optimization[edit]
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)
I've changed the algorithm to not use the equals operator, if !(A > B || B > A) then it doesn't really matter which one comes first, so it shouldn't affect sorting much anyway. Also, the new code makes the operator usage a parameter so you can now easily change the operator used and perform reverse sorting. --elmuerte 18:42, 17 September 2009 (UTC)
Instead of using array.Insert(index, 1) and array[index] = value, array.InsertItem(index, value) might be a bit more efficient. —Wormbo 16:51, 26 September 2009 (UTC)
