Algorithmes de tri

Rappels

En première, deux tris sont étudiés, le tri par insertion, et le tri par sélection. Nous reprenons dans ce tp ces deux tris, en en donnant une implémentation itérative opérant sur les tableaux, et une implémentation récursive opérant sur les listes chaînées. Nous verrons également d'autres tris, qui réalisent en moyenne moins d'opération de comparaison entre éléments.

On pourra également utiliser en complément les ressources suivantes :

• https://visualgo.net/bn/sorting Visualisation des algorithmes principaux de tri
• https://fr.wikipedia.org/wiki/Tri_par_insertion
• https://fr.wikipedia.org/wiki/Tri_par_sélection

Dans tout ce tp, le mot "élément" désignera des éléments de \(\mathbb{Z}\). Lorsque demandé par l'énoncé, on utilisera l'implémentation à l'aide des listes chaînées que l'on trouvera dans le fichier data_structures.py. On rappelle que la fonction ajoute prend deux arguments, une liste l et un élément e et renvoie la liste constituée de l'élément e suivi des éléments de l.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Maillon:bksl-nl """ Un maillon d'une liste chainée. """bksl-nl def py-undpy-undinitpy-undpy-und(self, v, s):bksl-nl """ int, Maillon -> None """bksl-nl self.valeur = vbksl-nl self.suivant = sbksl-nlbksl-nldef creerpy-undvide() -> Maillon: return Nonebksl-nldef estpy-undvide(m: Maillon) -> bool: return m is Nonebksl-nldef estpy-undsingleton(m: Maillon) -> bool: return not estpy-undvide(m) and estpy-undvide(queue(m))bksl-nldef ajoute(m: Maillon, e: int) -> Maillon: return Maillon(e, m)bksl-nldef tete(m: Maillon) -> int: return m.valeurbksl-nldef queue(m: Maillon) -> Maillon: return m.suivantbksl-nldef liste2str(m: Maillon) -> str: return f"{tete(m)} - {liste2str(queue(m))}" if not estpy-undvide(m) else "x"bksl-nldef affiche(m: Maillon) -> None: print(liste2str(m))bksl-nlbksl-nlbksl-nl# Listes exemplesbksl-nll1 = ajoute(ajoute(ajoute(ajoute(creerpy-undvide(), 9), 8), 6), 1)bksl-nll2 = ajoute(ajoute(ajoute(ajoute(creerpy-undvide(), 5), 1), 6), 3)bksl-nll3 = ajoute(ajoute(ajoute(creerpy-undvide(), 9), 7), 1)bksl-nll4 = ajoute(ajoute(ajoute(creerpy-undvide(), 8), 3), 2)bksl-nlbksl-nl

Vérifier qu'un tableau est trié

Écrire une fonction itérative tab_est_trié qui étant donné un tableau tab renvoie True si et seulement si ses éléments sont triés par ordre croissant, c'est à dire si pour tout \(i\in \mathbb{N}\) avec \(0 \leq i < n - 1\) (\(n\) est la taille du tableau), tab[i] <= tab[i + 1].

###

Lancer def testpy-undtabpy-undestpy-undtrie():bksl-nl """ Tests pour la fonction tabpy-undestpy-undtrie """bksl-nl print("Tests de tabpy-undestpy-undtrie passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tabpy-undestpy-undtriebksl-nl# testpy-undtabpy-undestpy-undtrie()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def tabpy-undestpy-undtrie(tab):bksl-nl """ [int] -> boolbksl-nl Détermine si le tableau tab est trié par ordre croissant. """bksl-nl passbksl-nlbksl-nl

Vérifier qu'une liste est triée

Écrire une fonction récursive liste_est_trié qui étant donné une liste l renvoie True si et seulement si ses éléments sont triés par ordre croissant.

###

Lancer def testpy-undlistepy-undestpy-undtriee():bksl-nl """ Tests pour la fonction listepy-undestpy-undtriee """bksl-nl print("Tests de listepy-undestpy-undtriee passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import listepy-undestpy-undtrieebksl-nl# testpy-undlistepy-undestpy-undtriee()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def listepy-undestpy-undtriee(l):bksl-nl """ Liste -> boolbksl-nl Détermine si la liste l est triée """bksl-nl passbksl-nlbksl-nl

Tri par insertion

Méthode itérative

On se propose dans cette partie de donner une implémentation itérative de l’algorithme du tri par sélection. La description itérative de cet algorithme est la suivante (n est la taille du tableau):

• à chaque étape, les i premières valeurs du tableau sont triées. Initialement, i vaut donc 0.

• tant que i n'est pas égal à n - 1, on insère l'élément d'indice i dans le sous-tableau trié constitué des éléments d'indice 0 (inclu) à i (exclu).

  Pour cela on opère par décalages successifs : en partant de l'élément d'indice i jusqu'à l'élément d'indice 1 on décale tous les éléments de la partie triée du tableau qui sont supérieurs à l'élément à insérer.

Jouer au jeu https://www.advanced-ict.info/interactive/insertion_sort.html, puis compléter le code de la fonction tri_insertion_iter ci-dessous pour que celle-ci corresponde à l'algorithme décrit dans l'énoncé.

###

Lancer def testpy-undtripy-undinsertionpy-unditer():bksl-nl """ Tests pour la fonction tripy-undinsertionpy-unditer """bksl-nl print("Tests de tripy-undinsertionpy-unditer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tripy-undinsertionpy-unditerbksl-nl# testpy-undtripy-undinsertionpy-unditer()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def tripy-undinsertionpy-unditer(tab):bksl-nl """ [int] -> [int]bksl-nl Trie en place le tableau tab (tri par insertion) """bksl-nl n = len(tab)bksl-nl for i in range(...):bksl-nl # les éléments d'indice 0..i du tableau tbksl-nl # sont triés dans l'ordre croissantbksl-nl element = tab[i]bksl-nl trou = ibksl-nl # on cherche à insérer l'élément dans le tableaubksl-nl # constitué des éléments d'indice 0..ibksl-nl while ... > ... and trou > 0:bksl-nl tab[trou] = ... # on décale l'élément précédent de tabbksl-nl trou = ... # mise à jour de l'indice du troubksl-nl # À la fin de la boucle soitbksl-nl # trou = 0 et tous les éléments de t sont supérieurs à élémentbksl-nl # soit trou > 0, t[trou - 1] < element < t[i] pour tout i >= troubksl-nl tab[trou] = ...bksl-nl # le tableau est alors triébksl-nl return tab # que se passe-t-il si on ne le met pas ?bksl-nlbksl-nl

Méthode récursive

L'objectif de cette partie est d'implémenter l'algorithme du tri par insertion, décrit ci-après.

• si la liste d'éléments à trier est vide, la liste triée est la liste vide ;
• si la liste d'éléments à trier n'est pas vide, on trie récursivement tous les éléments de la liste sauf le premier. Puis, on insère au bon endroit dans cette liste triée l'élément manquant, de telle sorte que la liste résultante soit également triée.

Soit \(l = (9, 42, 8, 12, 16)\).

1. Quelle est la liste de tout les éléments de \(l\) sauf le premier ?
2. Quelle est la liste triée de tous les éléments de \(l\) sauf le premier ? On appelle \(l_1\) cette liste.
3. On souhaite insérer un élément \(e\) dans une liste \(l_1\) supposée triée. Décrire en français les listes solution des questions suivantes. Vous devrez faire des phrases commençant par "C'est la liste constituée de", et en utilisant des expressions parmi "l'élément \(e\)", "la tête de \(l_1\)", "la queue de \(l_1\)", "suivit de", "les éléments de …", "les éléments de … où on a inséré l'élément …".
   1. Quelle est la liste attendue lorsque \(l_1\) est vide, et que \(e\) est un élément quelconque ?
   2. Lorsque \(l_1\) n'est pas vide :
      1. Quelle est la liste attendue lorsque \(e\) est plus petit que le premier élément de \(l_1\) ? (par exemple \(l_1 = (12, 16)\) et \(e = 9\))
      2. Quelle est la liste attendue lorsque \(e\) est plus grand que le premier élément de \(l_1\) ? (par exemple \(l_1 = (8, 12, 16)\) et \(e = 9\))

Insérer dans une liste triée

Afin d'implémenter l'algorithme du tri par insertion, on a besoin d'une fonction auxiliaire. La fonction insere_trie prend comme argument un élément e et une liste l d'éléments supposée triée, insère l'élément e dans la liste l de telle sorte que la liste résultante soit triée. En vous aidant des réponses à la question 3, écrire le code python d'une fonction récursive insere_trie qui réponde à l'énoncé. On rappelle que la fonction ajoute admet deux arguments l et e et renvoie la liste constituée de e suivi des éléments de l.

###

Lancer def testpy-undinserepy-undtrie():bksl-nl """ Tests pour la fonction inserepy-undtrie """bksl-nl print("Tests de inserepy-undtrie passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import inserepy-undtriebksl-nl# testpy-undinserepy-undtrie()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def inserepy-undtrie(l, e):bksl-nl """ Liste, int -> Listebksl-nl l est triée par ordre croissant """bksl-nl passbksl-nlbksl-nl

Tri par insertion

À l'aide de la fonction insere_trie, écrire une fonction trie_insertion_rec qui étant donnée une liste d'éléments l renvoie la liste des éléments de l triée dans l'ordre croissant. Vous utiliserez l'algorithme décrit dans l'introduction de cette section.

###

Lancer def testpy-undtriepy-undinsertionpy-undrec():bksl-nl """ Tests pour la fonction triepy-undinsertionpy-undrec """bksl-nl print("Tests de triepy-undinsertionpy-undrec passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import triepy-undinsertionpy-undrecbksl-nl# testpy-undtriepy-undinsertionpy-undrec()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def triepy-undinsertionpy-undrec(l):bksl-nl """ Liste -> Listebksl-nl Trie la liste l à l'aide de l'algorithme du tri par insertion """bksl-nl passbksl-nlbksl-nl

Tri par sélection

Méthode itérative

On se propose dans cette partie de donner une implémentation itérative de l’algorithme du tri par sélection. La description itérative de cet algorithme est la suivante (n est la taille du tableau et on prend comme exemple le tri du tableau [7, 5, 2, 8, 6, 4]) :

• On commence par rechercher le plus petit élément du tableau, puis on l’échange avec l’élément d’indice 0.

  Exemple. Le plus petit élément du tableau à partir de l'indice 0 est 2 que l'on échange avec 7. Le tableau devient [2, 5, 7, 8, 6, 4] - On recherche le plus petit élément du tableau à partir de l’élément d’indice 1, puis on l’échange avec l’élément d’indice 1.

  Exemple. Le plus petit élément du tableau à partir de l'indice 1 est 4 que l'on échange avec 5. Le tableau devient [2, 4, 7, 8, 6, 5]

• etc.

• On recherche le plus petit élément du tableau à partir de l’élément d’indice n − 1, puis on l’échange avec l’élément d’indice n − 1.

Minimum à partir d'un indice donné

Écrire une fonction mini_a_partir qui étant donné un tableau tab supposé non vide et un indice i renvoie l'indice du plus petit élément du tableau tab parmi les éléments d'indice compris entre i (inclu) et len(tab) (exclu).

###

Lancer def testpy-undminipy-undapy-undpartir():bksl-nl """ Tests pour la fonction minipy-undapy-undpartir """bksl-nl print("Tests de minipy-undapy-undpartir passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import minipy-undapy-undpartirbksl-nl# testpy-undminipy-undapy-undpartir()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def minipy-undapy-undpartir(tab, i):bksl-nl """ [int], int -> intbksl-nl Renvoie l'indice du plus petit élément de tab à partir de l'indice i """bksl-nl passbksl-nlbksl-nl

Tri par sélection

En déduire une fonction tri_selection_iter qui étant donné un tableau tab, renvoie un tableau constitué des éléments de tab triés par ordre croissant. On pourra modifier au passage le tableau initial tab.

###

Lancer def testpy-undtripy-undselectionpy-unditer():bksl-nl """ Tests pour la fonction tripy-undselectionpy-unditer """bksl-nl print("Tests de tripy-undselectionpy-unditer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tripy-undselectionpy-unditerbksl-nl# testpy-undtripy-undselectionpy-unditer()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def tripy-undselectionpy-unditer(tab):bksl-nl """ [int] -> [int]bksl-nl Trie le tableau tab (tri par sélection) """bksl-nl passbksl-nlbksl-nl

Méthode récursive

On se propose dans cette question de donner une implémentation récursive de l’algorithme de tri par sélection. La description récursive de cet algorithme est la suivante :

• Si la liste est vide alors la liste triée correspondante est la liste vide.
• Sinon, la liste triée est composée du plus petit élément mini de la liste suivi l de la liste triée des éléments de la liste l où l’on a supprimé un des éléments mini.

1. Soit \(l = (3, 42, 1, 8, 1, 12)\).
   1. Quel est le plus petit élément de l ?
   2. Quelle est la liste des éléments de l où l’on a supprimé un des plus petits éléments de l ?
2. Écrire les fonctions minimum, supprime et tri_selection_rec permettant d'implémenter une version récursive de l'algorithme de tri par sélection.

###

Lancer def testpy-undtripy-undselectionpy-undrec():bksl-nl """ Tests pour la fonction tripy-undselectionpy-undrec """bksl-nl print("Tests de tripy-undselectionpy-undrec passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tripy-undselectionpy-undrecbksl-nl# testpy-undtripy-undselectionpy-undrec()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def minimum(l):bksl-nl """ Liste -> intbksl-nl l est non videbksl-nl Renvoie le plus petit élément de la liste l """bksl-nl passbksl-nlbksl-nldef supprime(l, e):bksl-nl """ Liste, int -> Listebksl-nl l est non vide, e appartient à lbksl-nl Renvoie la liste l où on a supprimé une occurence de e """bksl-nl passbksl-nlbksl-nldef tripy-undselectionpy-undrec(l):bksl-nl """ Liste -> Listebksl-nl Trie la liste l (tri par sélection) """bksl-nl passbksl-nlbksl-nl

Tri fusion

Le tri fusion est un tri récursif qui met en place une technique dite de "diviser pour régner". Pour trier une liste l d'éléments, on peut :

• Diviser : séparer la liste l en deux listes l1 et l2 de mêmes tailles (à un élément près) ;
• Régner : trier récursivement les listes l1 et l2 en des listes l1_triée et l2_triée ;
• Combiner : fusionner les deux listes l1_triée et l2_trée en une liste triée l_triée

Soit \(l = (3, 42, 1, 8, 1, 12)\).

1. Donner deux listes l1 et l2, dont la longueur diffère d'au plus 1, et dont l'ensemble des éléments soient l'ensemble des éléments de la liste l.
2. Donner, sans justification, les listes l1_triée et l2_triée.
3. Expliquer comment obtenir à l'aide des deux listes l1_triée et l2_triée la liste l_triée.

Diviser

Écrire le code d'une fonction diviser qui étant donné une liste l renvoie deux listes de même taille (à un élément près), et dont l'ensemble des éléments soient l'ensemble des éléments de la liste l. On pourra s'inspirer de la manière de distribuer un jeu de carte (la liste) à deux joueurs :

• si il n'y a aucune carte, les deux joueurs ne reçoivent aucune carte ;
• s'il n'y a qu'une seule carte, le premier joueur reçoit une carte, le second aucune carte ;
• dans le cas général (il y a au moins deux cartes), on donne la première carte au premier joueur, la seconde carte au second joueur. Puis, on distribue les cartes restantes aux deux joueurs.

###

Lancer def testpy-unddiviser():bksl-nl """ Tests pour la fonction diviser """bksl-nl print("Tests de diviser passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import diviserbksl-nl# testpy-unddiviser()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def diviser(l):bksl-nl """ Liste -> Liste, Listebksl-nl Divise la liste en deux listes """bksl-nl passbksl-nlbksl-nl

Fusionner deux listes triées

Écrire le code python d'une fonction fusionner qui fusionne deux listes l1 et l2 supposées triées en une liste l triée dont les éléments sont les éléments de l1 et de l2. On pourra écrire une fonction itérative (en empilant successivement dans une pile auxiliaire la plus petite valeur entre les valeurs au sommet des piles l1 et l2) ou bien récursive.

###

Lancer def testpy-undfusionner():bksl-nl """ Tests pour la fonction fusionner """bksl-nl print("Tests de fusionner passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import fusionnerbksl-nl# testpy-undfusionner()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def fusionner(l1, l2):bksl-nl """ Liste, Listebksl-nl Renvoie la liste des éléments de l1 et l2 triés """bksl-nl passbksl-nlbksl-nl

Trier récursivement

1. Écrire une fonction tri_fusion qui trie récursivement la liste l de la manière suivante :
   • on séparer la liste l en deux listes l1 et l2 de mêmes tailles (à un élément près) ;
   • on trier récursivement les listes l1 et l2 en des listes l1_triée et l2_triée ;
   • on fusionne fusionner les deux listes l1_triée et l2_trée en une liste triée l_triée
2. Dresser l'arbre d'appel de l'instruction tri_fusion(l) où l est la liste \((3, 42, 1, 8, 1, 12)\).

###

Lancer def testpy-undtripy-undfusion():bksl-nl """ Tests pour la fonction tripy-undfusion """bksl-nl print("Tests de tripy-undfusion passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tripy-undfusionbksl-nl# testpy-undtripy-undfusion()bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def tripy-undfusion(l):bksl-nl """ Liste -> Listebksl-nl Trie la liste l (tri fusion) """bksl-nl passbksl-nlbksl-nl