Implantation des algorithmes de tri en Python

Tri à bulles (bubble sort)

Le tri à bulles est un algorithme de tri très simple dont le principe est de faire remonter à chaque étape le plus grand élément du tableau à trier, comme les bulles d’air remontent à la surface de l’eau (d’où le nom de l’algorithme).

Commençons par un exemple du fonctionnement de l’algorithme. Supposons qu’on souhaite trier la suite de nombres

Voici comment se passe le premier passage.

[5, 1, 2, 4, 3] # On compare 5 et 1 et on les inverse.
[1, 5, 2, 4, 3] # On compare 5 et 2 et on les inverse.
[1, 2, 5, 4, 3] # On compare 5 et 4 et on les inverse.
[1, 2, 4, 5, 3] # On compare 5 et 3 et on les inverse.
[1, 2, 4, 3, 5] # Fin du premier passage.

Comme on peut le voir, l’algorithme compare à chaque fois des éléments adjacents et les échange s’ils ne sont pas dans l’ordre. À la fin de ce premier passage, l’élément le plus grand du tableau (ici l’élément 5) se retrouve à la fin du tableau à sa position définitive. Le tableau n’est cependant pas encore complètement trié et nous devons donc continuer par un nouveau passage. Pendant ce nouveau passage on peut ignorer la dernière casse du tableau, car cette casse contient déjà l’élément le plus grand et ne nécessite donc pas d’être traité à nouveau.

[1, 2, 4, 3, 5] # On compare 1 et 2 et on ne fait rien.
[1, 2, 4, 3, 5] # On compare 2 et 4 et on ne fait rien.
[1, 2, 4, 3, 5] # On compare 4 et 3 et on les inverse.
[1, 2, 3, 4, 5] # Fin du deuxième passage

On recommence par faire un nouveau passage pour les 3 premières cases du tableau qui ne sont potentiellement pas encore dans l’ordre.

Voici le pseudo-code du tri à bulles (version non-optimisée), où est la longueur du tableau T à trier.

Tri-Bulles(T)
    pour i de n-1 à 1 // (pas -1)
        pour j de 0 à i - 1
            si T[j] > T[j+1]
               T[j] <-> T[j+1] // inverser T[j] et T[j+1]

:

L = random.sample(range(a, b), t)

Par exemple, pour générer une liste de 10 entiers compris entre 0 et 99 il suffit d’écrire :

>>> import random
>>> L = random.sample(range(0, 100), 10)
>>> L
[41, 21, 38, 20, 69, 14, 10, 50, 76, 9]

Tri par selection (selection sort)

Le tri par selection est encore un algorithme de tri qui a l’avantage d’être simple à mettre à l’oeuvre. L’idée de ce tri est la suivante : rechercher le plus petit élément du tableau et le placer à la première position. Rechercher ensuite le deuxième élément le plus petit et le placer en deuxième position. Continuer de la même façon jusqu’à ce que le tableau soit entièrement trié.

Le tableau est divisé en deux parties : la partie gauche des éléments déjà triés et la partie droite occupée par des éléments pas encore traités. Au début, la partie gauche est vide. L’algorithme recherche à chaque fois le plus petit élément de la partie droite (qui au débout est le tableau entier) et l’échange avec l’élément le plus à gauche de la partie de droite. À la fin de chaque étape la limite droite de la partie de gauche est avancé d’une position vers la droite.

Voici un exemple du fonctionnement de l’algorithme sur le tableau [10, 9, 5, 7, 3].

[10 9 5 7 3]     # Tableau à trier
[3| 9 5 7 10]    # 3 est le plus petit élément du tableau. 
                 # On l'échange avec 10. Sous-tableau gauche trié : [3]
[3 5| 9 7 10]    # On échange 5 (plus petit élément du sous-tableau droit)
                 # avec 9. Sous-tableau gauche trié : [3,5]
[3 5 7| 9 10]    # On échange 7 avec 9. Sous-tableau gauche trié : [3,5,7] 
[3 5 7 9| 10]    # Sous-tableau gauche trié : [3,5,7,9] 
[3 5 7 9 10]     # Sous-tableau gauche trié : [3,5,7,9,10]. Fin. 

Tri fusion (merge sort)

Le tri fusion se base sur le principe diviser pour régner.

  1. Appliquez le tri fusion à la main pour trier le tableau T = [5 2 4 7 1 3 2 6].

  2. Implémentez en Python le tri fusion vu en cours et testez-le sur un tableau de taille 1000 contenant des nombres aléatoires de 0 à 10000.

  3. Comparez en pratique son temps d’execution aux autres algorithmes de tri implantés précédemment.

Tri par paquets (bucket sort)

L’idée derrière ce tri est de distribuer les éléments à trier dans des urnes (ou paquets). Chaque urne est ensuite triée en utilisant un algorithme de tri efficace pour des entrées de petite taille, comme par exemple le tri d’insertion.

Dans l’exemple ci-dessous (source en.wikipedia.org), le tableau T = [29 25 3 49 37 21 43] est trié en utilisant le tri par paquets. Dans cet exemple on alloue cinq urnes. La première contiendra les éléments 0-9, la deuxième les éléments 10-19 etc. On mets chaque élément dans son urne correspondante et on trie tous les urnes une par une (en utilisant le tri par insertion par exemple). La dernière étape consiste à mettre le contenu de chaque urne bout-à-bout afin de créer le tableau trié.

Le tri par paquets fonctionne bien si les éléments sont uniformément distribués sur un espace. Dans ce cas, si le nombre des urnes est proportionnel au nombre d’éléments à trier, le temps d’exécution en moyenne est . Cependant, la complexité peut vite devenir quadratique si les éléments ne sont pas uniformément distribués et qu’il y’a donc des urnes qui contiennent beaucoup plus d’éléments que d’autres. Le pire cas survient notamment si tous les éléments à trier finissent dans une seule urne tandis que les autres urnes restent vides. Dans ce cas, la complexité est donné par le temps d’exécution du tri par insertion sur l’unique urne non-vide et ce temps est comme on le connaît quadratique.

  1. Implantez le tri par paquets en suivant les étapes suivantes :
  1. Testez votre implementation sur un tableau de grande taille généré aléatoirement. Comparez ses performances aux autres algorithmes de tri.

Autres algorithmes de tri

Implémentez les deux autres algorithmes de tri vus en cours (tri par insertion et tri rapide).