Discussion :

[bj303931]

Bonjour, je ne comprend pas pourquoi le pire cas du tri par sélection est 4(n-i)+3, en effet, pourquoi 4 et +3 ??? Et encore moins le meilleur (3(n-i+1).)

Tri par sélection:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
min <-i
pour j de i+1 à n faire
      si A[j]<A[min] alors
             min  <- j

Merci, pour votre précieuse aide.

[anapurna]

salut

est tu sur de ta complexité ?
pour un trie par sélection elle serait plus du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(n(n-1))/2

On effectue environ n échanges ;
La complexité moyenne et dans le pire des cas est quadratique (si vous doublez la taille d'un tableau, il vous faudra quatre fois plus de temps pour le trier).

[tbc92]

Je pense que dans son message, bjxxx définit la complexité de façon plus 'basique' que ce qui se fait de façon standard.

Il a un morceau de code , et a priori, l'objectif est de compter combien d'instructions seront exécutées.
Dans le pire scénario, l'instruction min <- i sera exécutée une fois
l'instruction pour j de i+1 à n faire sera exécutée n- (i+1) + 1+1 fois : J'imagine qu'on multiplie par 2 ... parce que en bas de la boucle Pour J..., on a un mot-clé de type GOTO
le test si A[j] < ... sera exécuté n- (i+1) + 1 fois
et comme on est dans le pire des cas, le test est toujours vrai, et la dernière instruction sera exécutée n- (i+1) + 1 fois

En trichant un peu, j'arrive ainsi à 4* (n-i) +3 instructions...

Et à l'opposé, dans le meilleur des cas, la dernière instruction n'est jamais exécutée.

Le comptage de 4(n-i)+3 et de 3 (n-i)+3 est un peu tiré par les cheveux, mais l'écart entre les 2 formules est incontestable : Entre le meilleur et le pire des scénarios, l'instruction min <- j est exécutée soit 0 fois, soit n-i fois. Ca fait bien un écart de n-i.

[bj303931]

ouais, merci...Tant pis!