3- Insertion d'un élément dans un tableau trié

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é).

Last modified: Saturday, 13 February 2021, 2:26 PM