> In an arbitrary step of Yade (not the first one), you have an ordered > list with just a few elements to move, and you will only compare > coordinates that are close to each other. > > I'm not claiming that the algorithm is perfect and I'm all for > improvement (and actually, I don't even know if it is still used in the > latest QuickSort collider), but at least it is not a N^2 algorithm.
InsertionSortCollider is typically over O(N*log N) depending on number of inversions (optimal O(N), worst case O(N^2)); bad enough given that there are algos which are _always_ O(N). QuickSort collider is much slower than InsertionSortCollider, since quicksort is optimal in the general case, but not for substantially pre-ordered lists... see http://yade.wikia.com/wiki/Colliders_performace (insertionsort is about 5x faster for non-initial steps). Cheers, Vaclav _______________________________________________ Mailing list: https://launchpad.net/~yade-users Post to : [email protected] Unsubscribe : https://launchpad.net/~yade-users More help : https://help.launchpad.net/ListHelp
