Aller au contenu

Insertion☘

On programme ici la partie insertion: comment insérer une nouvelle carte dans un tableau déjà trié.

Exercice☘

On rappelle que l'opérateur + entre deux listes a pour effet de créer une liste concaténation de la première liste et de la seconde.

>>> a = [42, 666]
>>> b = [1789, 1968]
>>> c = a + b
>>> c
[42, 666, 1789, 1968]

On considère le code suivant:

def insertion(tab, valeur):
    """
    tab -- liste d'entiers
    préconditions: 
        - liste est triée en ordre croissant
        - les éléments de liste sont tous distincts
    valeur -- entier

    renvoie .....
    """
    return [x for x in tab if x < valeur] + [valeur] + [x for x in tab if x >= valeur]
  • Quelle est la valeur de insertion([2, 3, 5, 6, 8], 3)?
  • Quelle est la valeur de insertion([2, 3, 5, 6, 8], 1)?
  • Quelle est la valeur de insertion([2, 3, 5, 6, 8], 9)?
  • Compléter la ligne "renvoie ..." du docstring.
Valeur renvoyée

La fonction renvoie une liste triée en ordre croissant contenant tous les éléments de tab et l'élément valeur.

Les valeurs demandées

On a indiqué les réponses en les ajoutant au docstring de la fonction.

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

    renvoie une liste
        - les éléments de liste sont les éléments de tab et valeur, 
        - liste est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 9)
    [2, 3, 5, 6, 8, 9]
    """
    return [x for x in tab if x < valeur] + [valeur] + [x for x in tab if x >= valeur]
  • Quel est le nombre de comparaisons effectuées lors d'une exécution de la fonction insertion? (ce nombre est fonction de la longueur n de la liste tab passée en paramètre).
Comparaisons?

On rappelle qu'une comparaison est l'utilisation de <, ou ==, ou >=, ou <=, ou >.

Nombre de comparaisons

Notons n la longueur de liste passée en argument.

  • Dans [x for x in tab if x < valeur], n comparaisons.
  • Dans [x for x in tab if x >= valeur], n comparaisons.

Au total, 2n comparaisons.

Exercice☘

Écrire un code possible pour la fonction suivante:

def rechercheIndicePivot(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.
    """
Un principe

Comme les éléments sont triés en ordre croissant, on les parcourt de gauche à droite et on s'arrête dès qu'on en a un qui est supérieur ou égal à la valeur pivot donnée en paramètre.

Solution

Un code possible:

def rechercheIndicePivot(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)

Exercice☘

On va ici réécrire la fonction d'insertion de l'exercice 1 mais en réduisant le nombre de comparaisons effectuées. Pour réduire ce nombre de comparaisons, nous utiliserons la précondition (qui n'a pas été utilisée dans la version de l'exercice 1): la liste donnée en paramètre est ordonnée. Cette précondition nous permet en effet de ne parcourir qu'une seule fois la liste (au lieu de deux dans la version précédente de l'insertion).

Insertion☘

Écrire une version de la fonction insertion de l'exercice 1 utilisant la fonction de l'exercice 2, cette fonction insertion n'utilisera aucune comparaison (ou plus exactement: toutes les comparaisons seront faites uniquement par la fonction rechercheIndicePivot).

def rechercheIndicePivot(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

    renvoie une liste
        - les éléments de liste sont les éléments de tab et valeur, 
        - liste est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 9)
    [2, 3, 5, 6, 8, 9]
    """
    indicePivot = rechercheIndicePivot(tab, valeur)
    # PARTIE A COMPLETER

Principe

La fonction rechercheIndicePivot() donne l'indice indicePivot auquel placer notre valeur.

On construit donc une liste en y plaçant:

  • en premier lieu, tous les éléments de tab ayant un indice < indicePivot (dans l'ordre de leurs indices puisqu'ils sont déjà en ordre croissant),
  • puis la valeur donnée en paramètre,
  • et enfin tous les éléments de tab ayant un indice ≥ indicePivot (dans l'ordre de leurs indices).
Solution

Un code possible:

def rechercheIndicePivot(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(atb) 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

    renvoie une liste dont les éléments sont les éléments de tab et valeur, la liste
    renvoyée est triée en ordre croissant. 
    >>> insertion([2, 3, 5, 6, 8], 3)
    [2, 3, 3, 5, 6, 8]
    >>> insertion([2, 3, 5, 6, 8], 1)
    [1, 2, 3, 5, 6, 8]
    """
    indice_pivot = rechercheIndicePivot(tab, valeur)
    return [tab[k] for k in range(indice_pivot)] + [valeur] + [tab[k] for k in range(indice_pivot, len(tab))]

Le nombre de comparaisons☘

Quel est maintenant le nombre de comparaisons effectuées lors d'un appel à la fonction insertion?

Réponse

Les comparaisons sont toutes effectuées dans l'appel à la fonction rechercheIndicePivot.

Notons n la longueur de la liste tab passée en argument.

  • Il peut y avoir 0 comparaison (cas de la liste vide).
  • Il peut y avoir une unique comparaison (cas tab[0] ≥ valeur).
  • Il peut y avoir deux comparaisons (cas tab[0] < valeur et tab[1] ≥ valeur).
  • Il peut y avoir trois comparaisons (cas tab[0] < valeur, tab[1] < valeur et tab[2] ≥ valeur).
  • ...
  • Il peut y avoir n comparaisons (cas tab[0], tab[1], ..., tab[n-2] tous < valeur et tab[n-1] ≥ valeur ou encore cas où tous les éléments sont < valeur).

Le nombre de comparaisons est donc compris entre 0 et n suivant la liste tab donnée en entrée. Nous avons donc réduit au moins de moitié le nombre de comparaisons par rapport à la version 1 de notre fonction d'insertion.