Tri par insertion

Le problème

  • Entrée : Un tableau $T$ de $n$ éléments $[t_0, t_1,\dots, t_{n-1}]$
  • Sortie : Une permutation $[t_0', t_1',\dots, t_{n-1}']$ du tableau d'entrée telle que $t_0'\leq t_1'\leq\dots\leq t_{n-1}'$.

Les tableaux seront implémentés en Python par des listes.

Le tri par insertion

L'algorithme du tri par insertion est la méthode qu'utilise généralement un joueur de cartes pour trier sa main. Il procède par étapes. Au début de l'étape numéro $k$, ses $k$ premières cartes, celles qui étaient situées à gauche au départ, sont toujours à gauche mais elles sont maintenant correctement triées. Lors de cet étape numéro $k$ le joueur choisit la carte située à la position $k$ et l'insère à la bonne place, de sorte que les $k+1$ cartes de gauche soient correctement triées. Si la main contient $n$ cartes, cette main est correctement triée au bout de $n-1$ étapes.

Question 1

Écrire le code de la fonction insertion.

In [ ]:
def insertion(T, k):
    """ Insère l'élément T[k] à la bonne place dans la liste T[:k+1]. 
        La liste T[:k] est supposée être déjà triée.
    """
    ### À COMPLÉTER
    
T = [1, 5, 8, 8, 9, 3, 4, 2]
insertion(T, 5)
print(T)      # -> [1, 3, 5, 8, 8, 9, 4, 2]

T = [1, 5, 8, 8, 9, 0, 4, 2]
insertion(T, 5)
print(T)      # -> [0, 1, 5, 8, 8, 9, 4, 2]

Question 2

Écrire le code de la fonction tri_insertion.

In [ ]:
def tri_insertion(T):
    """ Trie en place la liste T en utilisant l'algorithme
        du tri par insertion.
    """
    ### À COMPLÉTER
    
T = [4, 6, 2, 4, 0, 1]
tri_insertion(T)
print(T)      

Question 3

(a) Lors de l'exécution de tri_insertion, quelle est l'instruction de insertion qui est exécutée le plus grand nombre de fois ?

(b) Combien de fois au minimum cette instruction est-elle exécutée ? Dans quelle situation ce minimum est-il atteint ?

(c) Combien de fois au maximum cette instruction est-elle exécutée ? Dans quelle situation ce maximum est-il atteint ?

Trier en utilisant des piles

Vous disposer d'un tas de cartes que vous souhaitez trier par ordre de valeur, la carte la plus faible devant se trouver sur le sommet du tas.

Le tas est initialement sur un emplacement $T$. Vous avez à votre disposition deux autres emplacements $C$ et $D$ sur lesquels vous pouvez empiler des cartes. Les seules actions autorisées sont :

  • Choisir une carte sur l'un des sommets $T$, $C$ ou $D$
  • Placer la carte choisie sur l'un des sommets $T$, $C$ ou $D$.

Question 4

Concevoir une méthode pour trier le tas de cartes.

Découper une feuille en 16 morceaux de même taille, numéroter les morceaux de 1 à 16, les mélanger et les placer sur un tas $T$. Appliquer votre algorithme.

Question 5

Reprendre l'algorithme précédent pour écrire une fonction tri_piles(T) qui trie la liste T en utilisant deux listes auxilliaires C et D.

On peut utiliser une liste python en tant que pile en considérant que le dernier élément de la liste correspond au sommet de la pile.

Instruction Effet
L = [] Crée une pile vide
L[-1] Lecture du sommet de la pile
L.append(x) Ajout de la valeur x au sommet de la pile
x = L.pop() Lecture et retrait de l'élément au sommet de la pile

Afin d'éviter de devoir tester les cas particuliers où les piles C ou D sont vides, une astuce consiste à placer initialement au fond de la pile C un nombre plus grand que tous les autres et au fond de la pile D un nombre plus petit que tous les autres.

In [ ]:
def tri_piles(T):
    """ Trie la liste T à l'aide de deux piles auxilliaires.
    """
    ### À COMPLÉTER
        
T = [4, 6, 2, 4, 0, 1]
tri_piles(T)
print(T)          

Coût moyen du tri par insertion

On revient dans cette partie sur la fonction tri_insertion(T). Le temps d'exécution de cette fonction dépend de façon évidente du nombre $n$ d'éléments à trier. Nous avons également vu que ce temps n'est pas le même pour tous les tableaux de même taille. Nous souhaitons maintenant voir comment évolue le temps moyen d'exécution en fonction de $n$.

Question 6

Écrire une fonction simul(n) qui trie 10 listes aléatoires de taille $n$ et qui retourne le temps moyen d'exécution.

  • La fonction random.random() retourne un flottant aléatoire entre 0 et 1.

  • La fonction time.time() retourne le timestamp, c'est-à-dire le nombre de secondes écoulées depuis le 1er janvier 1970 à 0h00.

In [ ]:
 

Question 7

Utiliser la fonction simul pour observer empiriquement la façon dont évolue le temps moyen d'exécution de tri_insertion(T) en fonction du nombre $n$ d'éléments de T.

In [ ]:
 

Question 8

Retrouver le résultat précédent en raisonnement sur l'algorithme.

Le tri Shell

Le tri Shell est une amélioration du tri par insertion qui est basé sur les deux observations suivantes :

  • Le tri par insertion est efficace si la liste est à peu près triée ;
  • Le tri par insertion est inefficace en moyenne car il ne déplace les valeurs que d'une position par instruction.

Pour mettre en oeuvre le tri Shell sur un tableau T on choisit un entier positif $s$. On utilise alors l'algorithme de tri par insertion pour trier entre eux les éléments dont les indices sont des multiples de $s$. On trie de même entre eux les éléments dont l'indice est congru à 1 modulo $s$. On poursuit ainsi jusqu'à trier entre eux les éléments dont l'indice est congru à $s-1$ modulo $s$.

On a ainsi rapproché les éléments de T de leurs positions correctes par des sauts de longueur $s$. On recommence alors le même traitement en choisissant des valeurs de $s$ de plus en plus petites. La dernière valeur de $s$ choisie est 1 ce qui conduit à faire un tri par insertion classique mais sur un tableau qui est déjà à peu près trié.

En pratique les valeurs de $s$ optimales (trouvées empiriquement) sont : 1, 4, 10, 23, 57, 132, 301, 701.

Question 9

Écrire le code de la fonction tri_shell.

In [ ]:
def tri_shell(T):
    """ Trie en place la liste T en utilisant 
        l'algorithme de tri de Shell.
    """
    ### À COMPLÉTER

T = [4, 6, 2, 4, 0, 1]
tri_shell(T)
print(T)  

Question 10

Comparer expérimentalement l'efficacité relative des fonctions tri_insertion et tri_shell.

In [ ]: