Aller au contenu

Insertion en place☘

Exercice 1☘

On aimerait maintenant écrire une fonction insertion qui ne renvoie pas une nouvelle liste. On veut donc écrire une fonction (avec effet de bord) qui modifie la liste donnée en argument.

def insertion(tab, valeur):
    """
    tab -- liste d'entiers, 
    précondition: liste est triée en ordre croissant
    valeur -- entier

    Modifie tab en insérant valeur dans tab 
    de telle façon que tab soit encore triée en ordre croissant
    après ajout de valeur. 

    (renvoie None)
    """
Exemple d'utilisation:

>>> A = [2, 4, 5]
>>> insertion(A, 1)
>>> A
[1, 2, 4, 5]
>>> B = [2, 4, 5]
>>> insertion(B, 4)
>>> B
[2, 4, 4, 5]
>>> C = [2, 4, 5]
>>> insertion(C, 9)
>>> C
[2, 4, 5, 9]

Proposer un code satisfaisant la demande.

Aide 1

On pourra utiliser la fonction déjà vue ci-dessous:

def rechercheIndice(tab, valeur):
    """
    tab -- liste d'entiers, 
    précondition: tab triée en ordre croissant
    valeur -- entier

    renvoie le plus petit indice i tel que tab[i] >= valeur
    et renvoie len(tab) si un tel indice n'existe pas.
    """
    for indice, element in enumerate(tab):
        if element >= valeur: return indice
    return len(tab)
Aide 2: un descriptif possible
  • On calcule l'indice auquel placer valeur (avec rechercheIndicePivot).
  • On ajoute une "place" en fin de liste.
  • On remonte d'un rang tous les éléments >= valeur (ce sont ceux qui ont un indice supérieur ou égal à l'indice calculé pour la valeur à insérer).
  • On place valeur.
Solution

Un code possible:

def rechercheIndice(tab, valeur):
    """
    tab -- liste d'entiers, précondition: tab triée en ordre croissant
    valeur -- entier

    renvoie le plus petit indice i tel que tab[i] >= valeur
    et renvoie len(tab) si un tel indice n'existe pas.
    """
    for indice, element in enumerate(tab):
        if element >= valeur: return indice
    return len(tab)



def insertion(tab, valeur):
    """
    tab -- liste d'entiers, 
    précondition: liste est triée en ordre croissant
    valeur -- entier

    Modifie tab en insérant valeur dans tab 
    de telle façon que tab soit encore triée en ordre croissant
    après ajout de valeur.   
    """
    lg = len(tab) # nombre initial d'éléments
    # on calcule l'indice auquel placer le nouvel élément:
    indice_pivot = rechercheIndice(tab, valeur)
    # on ajoute une "place" en fin de liste:
    tab.append(0)
    # on remonte d'un rang dans la liste tous les éléments >= valeur
    # càd les éléments d'indices entre indice_pivot et lg-1:
    for k in range(lg-1, indice_pivot-1, -1):
        tab[k+1] =  tab[k]
    # on place valeur dans le "trou" ainsi créé:
    tab[indice_pivot] = valeur

Testez...

Exercice 2☘

On suppose maintenant que l'on dispose d'une liste dont les k premiers éléments (d'indices entre 0 et k-1) sont triés en ordre croissant.

Et on aimerait qu'après appel à une nouvelle fonction insertion les k+1 premiers éléments (ceux d'indices entre 0 et k) soient triés en ordre croissant. En d'autres termes, l'élément "valeur" des fonctions précédentes est l'élément d'indice k de la liste et il s'agit de le placer correctement.

def rechercheIndicePivot(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    renvoie le plus petit indice i ( 0 <= i <= k-1) 
    tel que tab[i] >= tab[k]
    et renvoie k si un tel indice n'existe pas.
    """


def insertion(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    Modifie tab, en sortie:
        - tab contient les mêmes éléments qu'en entrée
        - tab[0..k] est triée en ordre croissant
        - Chaque élément de tab[k+1..] est inchangé.

    """

Exemple d'utilisation:

>>> A = [2, 4, 5, 1, -2]
>>> insertion(A, 3)
>>> A
[1, 2, 4, 5, -2]
>>> A = [2, 4, 5, 4, -2]
>>> insertion(A, 3)
>>> A
[2, 4, 4, 5, -2]  
>>> A = [2, 4, 5, 9, -2]
>>> insertion(A, 3)
>>> A
[2, 4, 5, 9, -2]

Important

Attention, le second paramètre k n'est plus, comme dans les exercices précédents, la valeur à placer mais l'indice de la valeur à placer.

A vous: adapter les fonctions rechercheIndicePivot et insertion des exercices précédents à la situation proposée ici.

Un code possible
def rechercheIndicePivot(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    renvoie le plus petit indice i ( 0 <= i <= k-1) 
    tel que tab[i] >= tab[k]
    et renvoie k si un tel indice n'existe pas.
    """
    valeur = tab[k]
    for indice in range(0, k):
        if tab[indice] >= valeur: return indice
    return k



def insertion(tab, k):
    """
    tab -- liste d'entiers, 
    k -- entier, 0 < k < len(tab)
    précondition: tab[0..k-1] est triée en ordre croissant

    Modifie tab, en sortie:
        - tab contient les mêmes éléments qu'en entrée
        - tab[0..k] est triée en ordre croissant
        - Chaque élément de tab[k+1..] est inchangé.
    >>> A = [2, 4, 5, 1, -2]
    >>> insertion(A, 3)
    >>> A
    [1, 2, 4, 5, -2]
    >>> A = [2, 4, 5, 4, -2]
    >>> insertion(A, 3)
    >>> A
    [2, 4, 4, 5, -2]  
    >>> A = [2, 4, 5, 9, -2]
    >>> insertion(A, 3)
    >>> A
    [2, 4, 5, 9, -2]    
    """
    valeur = tab[k]
    # on calcule l'indice où placer valeur:
    indicePivot = rechercheIndicePivot(tab, k)
    # on remonte d'un rang tous les éléments >= valeur:
    for j in range(k-1, indicePivot-1, -1):
        tab[j+1] = tab[j]
    # on place valeur à sa nouvelle position:
    tab[indicePivot] = valeur