Les tris

Quand on a une liste de valeurs aléatoires (ou pas), et qu'on veut les trier, on utilise un algorithme de tri, car cela ne se fait pas en un claquement de doigts. Mais lequel choisir?

Règle n°1: on peut juste échanger les valeurs une par une dans une liste

Le tri à bulles

Pour ce premier tri, assez simple, consiste à parcourir toute la liste avec une sorte de "bulle" qui englobe à chaque fois deux valeurs et les inverse si elles ne sont pas dans le bon ordre elle reparcourt ainsi encore et encore la liste jusqu'à avoir tout trié.

Exemple:

Liste :

[1, 5, 89, 14, 51, 12]

[1, 5, 14, 89, 51, 12]

Premier parcourage de liste: La bulle avance tout le long, elle inverse le valeurs quand elles sont dans l'odre décroissant, sinon, elle ne fait rien. On remarquera que le 89, valeur la plus grosse est mise en fin de liste.

[1, 5, 14, 51, 89, 12]

[1, 5, 14, 51, 12, 89]

Deuxième parcourage de liste: On a pas tellement avancé ce coup ci, on à eu qu'une seule inversion à faire.

[1, 5, 14, 51, 12, 89]

[1, 5, 14, 12, 51, 89]

[1, 5, 12, 14, 51, 89]

Troisième (et dernier) parcourage de liste: Encore une fois, on ne bouge que le 12 mais cette fois on a finalement notre liste triée!

Nombre d'étapes: 20 (et encore, pour que le code sache qu'il a tout trié, il doit refaire un tour de liste pour voir qu'il n'a plus rien à trier. Soit Liste éléments = 6 --> 20+6 = 26)

[1, 5, 12, 14, 51, 89]

Bilan: Ce tri fonctionne bien, mais il reste assez lent car il fait beaucoup de tours de liste.

Le tri par fusion

Nouveau tri, nouvelle notion. Voici comment ce tri fonctionne: On divise notre liste en sous listes de 2 éléments,(si il y a un nombre impair, on non divisible par un nombre pair, on rajoute un ou des élément(s) en plus, qui ne sera(ons) pas trié)qui vont être triés(voici comment ça marche: on prend la plus petite valeur et on la met dans la liste plus grande, puis on répète l'opération…), listes qu'on va ensuite fusionner deux par deux puis les retrier pour les fusionner encore deux par deux pour les trier… Etc... Jusqu'à ce qu'on ait trié toute la liste.(à noter que ça marche sans encombre si la longueur de la liste est proche ou dans les puissances de 2(2,4,8,16,32,64,128,256,512,1024...))

Exemple:

Liste :

[1, 5, 89, 14, 51, 12, 40, 33]

[1, 5] [89, 14] [51, 12] [40, 33]

[1, 5] [14, 89] [12, 51] [33, 40]

Nombre d'étapes: 6 (mais attention, cette information est à prendre avec des pincettes, car je ne connais pas la manière de trier les sous listes de cet algorithme, disons que dans le pire des cas, le nombre d'étapes est de 24 pour une liste de 8 éléments, dans le cas échéant, celle ci.)

[1, 5, 14, 89] [12, 51, 33, 40]

[1, 5, 14, 89] [12, 33, 40, 51]

[1, 5, 12, 14, 33, 40, 51, 89]

Bilan: Plus rapide que la moyenne, c'est un bon tri, mais on peut quand même faire mieux.

Le tri par sélection du minimum

Pour ce tri là, on fonctionne différemment du dernier, voilà comment on procède:

Tout d'abord, on cherche la valeur la plus petite de la liste puis on la dépose dans une deuxième liste avec la commande liste.pop et liste2.append.

Exemple:

Liste :

[1, 5, 89, 14, 51, 12]

__________________________

Nb d'étapes= 6

[1, 5, 89, 14, 51, 12]

Liste 2 :

[1, , , , , ]

Nb d'étapes= +2

__________________________

[5, 89, 14, 51, 12]

Nb d'étapes= +5

__________________________

[5, 89, 14, 51, 12]

[1,5, , , , ]

Nb d'étapes= +2

__________________________

[89, 14, 51, 12]

Nb d'étapes= +4

__________________________

[89, 14, 51, 12]

[1,5,12, , , ]

Nb d'étapes= +2

__________________________

[89, 14, 51]

Nb d'étapes= +3

__________________________

[89, 14, 51]

[1,5,12,14, , ]

Nb d'étapes= +2

__________________________

[89, 51]

Nb d'étapes= +2

__________________________

[89, 51]

[1,5,12,14,51 , ]

Nb d'étapes= +2

__________________________

[89]

__________________________

Nb d'étapes= +1

[89]

[1,5,12,14,51,89 ]

Nombre d'étapes: 6+2+5+4+3+2+1+2=33 (wsh c'est lent)

Nb d'étapes= +2

Bilan: Ce tri fonctionne bien, mais il est très lent car il fait autant de tours de liste que le nombre d'éléments de la liste au carré.

Le tri par insertion

Alors, que dire du tri par insertion? Déjà il fonctionne un peu comme le tri par sélection, mais il a quand même son fonctionnement bien à lui:

D'abord, on prend la première valeur d'une liste puis on la met dans une autre liste. On fait pareil avec la valeur d'après, en prenant soin qu'elle soit placée au bon endroit dans la deuxième liste. On répète l'opération jusqu'à ce qu'on ait tout trié.

Exemple:

Liste :

[1, 5, 89, 14, 51, 12]

[1, ]

Liste 2 :

[1, 5, 89, 14, 51, 12]

[1, 5]

Bon là je passe des trucs, mais il faut aussi plusieurs étapes pour mettre la valeur au bon endroit , c'est à dire avant une valeur plus grande qu'elle.

[1, 5, 89, 14, 51, 12]

[1, 5, 89]

[1, 5, 89, 14, 51, 12]

[1, 5, 14, 89]

[1, 5, 89, 14, 51, 12]

[1, 5, 14, 51, 89]

[1, 5, 89, 14, 51, 12]

[1, 5, 12, 14, 51, 89]

Nombre d'étapes: Pas mal (environ 25)

Bilan: A l'instar de son cousin sélection, ce tri est LENT.

Le tri rapide

BON....Je vous fait pas un dessin, ce tri est RAPIDE. Surtout pour les grosses listes(parce que pour les petites c'est un peu moins efficace). Alors comment ça marche? Ben d'abord on va définir une valeur "pivot" au sein de la liste dans laquelle on va mettre à gauche de cette valeur toute les valeurs plus petite et à droite toute les plus grandes. Et on refait ça avec des bouts plus petits.

[1, 5, 89, 14, 51, 12]

Notre liste bien aimée:

[1, 5, 89, 14, 51, 12]

Valeur pivot (choisie au hasard)

[1, 5, 12, 14, 51, 89]

Nombre d'étapes: 4!!!! QUEL COUP DE CHANCE EXTRAORDINAIRE!!!!!

Bilan: Ben kwa? Je vous avait dit que c'était efficace.

sort et sorted

Dans Python, si on veut pas se casser la tête, au lieu de créer soi même un algorithme de tri on peut écrire dans son code liste.sort (ou liste.sorted).

Mais qu'est ce que quoi que comment que ça fait pour trier votre liste ça?

D'abord sort: Quand vous le mettez à coté de votre liste après un point, ça va utiliser le pour trier votre liste.

Mais vous voulez garder votre liste tel qu'elle est et juste avoir une copie de celle ci mais triée? à aucun moment je vois à quoi ça pourrait servir mais NE VOUS IN-QUIE-TEZ PAS!!!!! GRACE A LA SUUUUUUUUUUUUPER METHODE sorted , SOYEZ PRET A FAIRE UNE COPIE DE VOTRE LISTE A TOUT MOMENT!!!!!!!

Revenir au Tp

Revenir à l'acceuil