Tri insertion en place

Exercice

Utiliser la fonction insertion de la page précédente (code rappelé ci-dessous)

Rappel de insertion avec effet de bord

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

pour écrire un code possible pour la fonction suivante:

def triInsertion(tab):
    """
    tab -- liste d'entiers

    Modifie tab en triant ses éléments en ordre croissant
    (fonction à effet de bord, ne renvoie rien)
    """

On trie maintenant en place la liste passée en argument.

Solution

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


def triInsertion(tab):
    """
    tab -- liste d'entiers

    Modifie tab en triant ses éléments en ordre croissant
    (fonction à effet de bord, ne renvoie rien)
    """
    for k in range(1, len(tab)):
        insertion(tab, k)




#### TESTS 
from random import randint

A = [randint(-10, 10) for k in range(randint(5,10))]
print(A)
B = [x for x in A] # copie de A 
triInsertion(A)
print(A)
# on teste notre tri en utilisant la méthode sort prédéfinie en python:
B.sort()
print(A == B)

Pour aller plus loin

Hors programme

Dans le programme de terminale NSI, on travaille la récursivité. Cette notion n'est pas au programme de la première. La suite est donc à ne lire que si vous voulez aller plus loin.

Ci-dessous une version récursive du tri par insertion:

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]
    indice = k-1
    while indice >= 0 and tab[indice] > valeur:
        indice -= 1
    return indice+1



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




def tri_insertion_recursif(tab, n):
    """
    tab -- liste d'entiers
    n -- indice d'un élément de tab

    Modifie tab en triant ses éléments en ordre croissant
    (fonction à effet de bord, ne renvoie rien)
    """
    if n > 0:
        tri_insertion_recursif(tab, n-1)
        insertion(tab, n)



#### TESTS 
from random import randint

A = [randint(-10, 10) for k in range(randint(5,10))]
print(A)
B = [x for x in A] # copie de A 
tri_insertion_recursif(A, len(A)-1)
print(A)
# on teste notre tri en utilisant la méthode sort prédéfinie en python:
B.sort()
print(A == B)