Algorithmique et Structures de Données

Solution :

Algorithme (Insert) :
Entrées :
• Tableau tab, max_taille éléments alloués
éléments 0 ≤ i < taille < max_taille initialisés.
• un élément e.
Précondition : tab est trié (tab[i] ≤ tab[i + 1]).
Effet : e ajouté à tab trié.

Début
    i <- taille
    tant que i > 0 et tab[i-1] > e faire
         tab[i] <- tab[i-1]
         i <- i-1

     fintantque
     tab[i] <- e
     taille <- taille + 1

Fin.

=>Complexité : O(N). (Ajouter les détailles de calcul de la complexité).