yade-users team mailing list archive

[Bruno Chareyre <bruno.chareyre@xxxxxxxxxxx>]

> 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).
>
>   
1000xN is worst than 0.0001xN^2 for practical problems, right? ;)

For instance : TriangulationCollider is O(N), but I never use it, 
because it is the slowest collider in Yade currently.

> 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).
>
>   
Yes, sorry, I was thinking about InsertionSort (the new one), not QuickSort.


Bruno

--

_______________
Chareyre Bruno
Maître de Conférences

Grenoble INP
Laboratoire 3SR - bureau E145
BP 53 - 38041, Grenoble cedex 9 - France
Tél : 33 4 56 52 86 21
Fax : 33 4 76 82 70 43
________________