Poste | Agent De Tri – Agir | Générateur De Réussite Depuis 1992
La complexité du tri par insertion reste linéaire si le tableau est presque trié (par exemple, chaque élément est à une distance bornée de la position où il devrait être, ou bien tous les éléments sauf un nombre borné sont à leur place). Dans cette situation particulière, le tri par insertion surpasse d'autres méthodes de tri: par exemple, le tri fusion et le tri rapide (avec choix aléatoire du pivot) sont tous les deux en même sur une liste triée. Variantes et optimisations Optimisations pour les tableaux Plusieurs modifications de l'algorithme permettent de diminuer le temps d'exécution, bien que la complexité reste quadratique. On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés. Trie par insertion point. Il est possible d'implémenter cette variante de sorte que le tri soit encore stable.
Trie Par Insertion Point
Lors d'un exercice précédent, nous avons vu que la complexité temporelle du tri par insertion (tel que présenté en cours) est en \(O(n^2)\). La complexité temporelle de la méthode insertion_sort est différente, cependant. Pouvez-vous identifier la raison de cette différence? [TP08] Tri par insertion - insertion_sort - [LINFO1103] Introduction à l'algorithmique | INGInious. Selectionnez, parmi les propositions suivantes, celle ou celles qui justifient cette augmentation de la complexité temporelle de ìnsertion_sort` par rapport au tri vu en cours.
\(T(n)=0\) \(T(v)=0\) \(T(\frac{n}{2})=b\) \(T(n-1)=b\) \(T(n-1)=0\) \(T(\frac{n}{2})=1\) \(T(0)= b_1 + b_2\) \(T(0)=v\) \(T(n)=n\) \(T(0)=b\) \(T(n \leq v)=n\) Sélectionnez, parmi les réponses proposées, celle qui définit le cas général de la récurrence de la fonction insertion_sort_h.