Complexité d'un algorithme de tri

Bonjour !

J'ai un exercice qui est le suivant :

On cherche à trier un tableau de n entiers dont seulement p éléments ne sont pas à leur place (si on retire ces p éléments, les n-p restants sont bien dans l'ordre). Quelle est la complexité au pire des cas d'un tri par insertion sur un tel tableau ? Justifier votre réponse.

Je suis débutante en algorithme et notion de complexité. Quelqu'un peut-il me proposer une solution ou me mettre sur le bon chemin pour comprendre la notion de complexité de tri des tableaux ? Merci d'avance !

Bonjour,

Le problème est celui-ci : les tris doivent être rapides afin d'immobiliser le moins longtemps possible la machine et l'utilisateur. On ne calcule pas en temps (car dépendant de la machine), mais en opérations à effectuer. Ici, l'opération de base est la comparaison des entiers du tableau. Afin de calculer la complexité du tri, on se place dans le pire des cas :mouarf:

Si je dois insérer un M-ième élément dans mon tableau, je vais devoir au pire comparer mon nouvel entier avec tous ceux déjà triés, soit M-1 éléments. J'aurai alors M éléments après l'insertion.
Si j'en insère un autre, je devrais cette fois-ci balayer, au pire, M éléments pour en obtenir M+1...
Je boucle ainsi jusqu'au dernier élément à insérer. Le nombre de comparaisons a toujours un temps de retard sur le nombre d'éléments triés.
SI j'avais commencé par un élément, j'aurais donc effectué :
Total = 1 + 2 + 3 + ... + M-2 + M-1 comparaisons.
On sait que cette somme peut s'écrire M-1 + M-2 + M-3 + ... + 2 + 1 = Total.

On a donc, en additionnant les deux :
2 Total = M + M + M + ... + M + M [=> M-1 fois]
Donc Total = M (M-1)/2
Sachant que M(M-1) est proche de M² si M est très grand et que le rapport /2 n'a pas de sens pour deux ordinateurs aux vitesses différentes, on dira que l'ordre de complexité du tri est M².

Ce n'est pas la réponse au problème, mais le principe devrait y être. Un vrai mathématicien devrait affiner le raisonnement et le rendre plus rigoureux :zoubi:

Cordialement

Le pire des cas est si les éléments doivent etre remontés par les autres éléments.

Donc par exemple, que les éléments déja triés soient les plus grands, mais qu'ils soient au début du tableau. Ou bien qu'ils soient les plus petits et qu'ils soient a la fin du tableau. Et pour les éléments additionnels qu'ils soient en ordre décroissant.

Si les éléments déja triés sont tous traversés, cela donne n-p comparaison pour chaque élément additionnel, donc (n-p)*p pour traverser les éléments déja triés.

Pour le tri des éléments supplémentaires entre eux, s'ils sont en ordre décroissant, cela ajoute 1+2+3...+(p-2)+(p-1) = p*(p-1)/2

Enfin pour les éléments déja triés, il faut ajouter 1 pour chacun, donc cela ajoute n-p ou pour etre exact max(n-p-1,0)

Donc un total de:

(n-p)*p + p*(p-1)/2 + n-p

ce qui donne n si p = 0
et donne p*(p-1)/2 si p = n