yade-users team mailing list archive

[Václav Šmilauer <eudoxos@xxxxxxxx>]

> 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