Posté par nlhss .
En réponse au journal Java (EE) Sapu cépalibre..
Évalué à 0.
Dernière modification le 15 juillet 2016 à 12:15.
C'est une histoire de complexité asymptotique, de pire cas VS cas moyen VS cas favorable, etc.
Par exemple, sur un tableau déjà trié, un algo asymptotiquement en O(n2) peut être plus efficace qu'un algo en O(Nlog(N)) car ce dernier va faire des tas d'accès inutiles, voire même éventuellement déplacer des éléments alors que ce n'était pas nécessaire.
When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).
(wikipédia).
En gros le tri par insertion, malgré sa plus grande complexité que le quick sort, est plus efficace sur des ensembles déjà trié ou partiellement triés.
[^] # Re: migre
Posté par nlhss . En réponse au journal Java (EE) Sapu cépalibre.. Évalué à 0. Dernière modification le 15 juillet 2016 à 12:15.
C'est une histoire de complexité asymptotique, de pire cas VS cas moyen VS cas favorable, etc.
Par exemple, sur un tableau déjà trié, un algo asymptotiquement en O(n2) peut être plus efficace qu'un algo en O(Nlog(N)) car ce dernier va faire des tas d'accès inutiles, voire même éventuellement déplacer des éléments alors que ce n'était pas nécessaire.
En gros le tri par insertion, malgré sa plus grande complexité que le quick sort, est plus efficace sur des ensembles déjà trié ou partiellement triés.