24-NSIJ2AN1-1

Énoncé Sujet

def echange(tab, i, j):
    tab[i], tab[j] = tab[j], tab[i]

Ou plus simplement :

def echange(tab, i, j):
    copie  = tab[i]
    tab[i] = tab[j]
    tab[j] = copie

def triStooge(tab, i, j):
    if tab[i] > tab[j]:
        echange(tab, i, j)
    if j - i > 1:
        k = (j - i + 1) // 3
        triStooge(tab, i, j - k)
        triStooge(tab, i + k, j)
        triStooge(tab, i, j - k)

Cet algorithme est récursif car la fonction triStooge fait appel à elle-même (ligne 6 à 8).
Lors du premier appel, i = 0 et j = 5 donc k = (5 – 0 + 1) // 3 = 2.
Sans compter l'appel initial, le nombre d'appels récursifs est 39 en comptant le nombre de nœuds, en excluant la racine, de l'arbre des appels.
- Case 1 : triStooge(A, 1, 3)
- Case 2 : triStooge(A, 2, 3)
- Case 3 : triStooge(A, 0, 3)

Appel	Valeur de `A` avant l'appel	Valeur de `A` après l'appel
`triStooge(A, 0, 3)`	`[5, 6, 4, 2]`	`[2, 6, 4, 5]`
`triStooge(A, 0, 2)`	`[2, 6, 4, 5]`	`[2, 6, 4, 5]`
`triStooge(A, 1, 3)`	`[2, 4, 6, 5]`	`[2, 4, 6, 5]`
`triStooge(A, 0, 2)`	`[2, 4, 5, 6]`	`[2, 4, 5, 6]`

Puisque \(2 = \frac{6}{3} < \frac{8}{3}\), le tri par insertion (ou le tri par sélection) dont le coût en temps dans le pire des cas est quadratique \(O(n^2)\), présente un meilleur coût. On aurait pu aussi citer le tri fusion de complexité quasilinéaire \(O(n \log n)\).