Algorithmes de tri

jeudi 8 mars 2012
par  Webmestre

Depuis longtemps les tris ne sont plus un problème en algorithme. Il y a en plusieurs plus ou moins efficaces, encore faut-il les connaître !

Pour s’en faire une idée assez simplement, il suffit de s’observer ramasser ses cartes au tarot (ou à n’importe quel jeu de cartes) :

  • Vous les prenez toutes ensemble dans la main et vous les... triez (oui oui), alors vous faites certainement un tri à bulle,
  • vous ramassez les cartes une à une en les insérant au bon endroit : vous faites le tri par... insertion !

Voilà une première approche. Mais il en existe d’autres, et l’université de Sapientia en Roumanie a choisi d’illustrer ces algorithmes avec des danses en utilisant des musiques traditionnelles, où chaque danseur est un numéro dans un tableau d’entiers non triés.

C’est amusant et pédagogique ; suivez les liens.

Tout d’abord, le plus facile à comprendre le tri par insertion.

Le tri à bulle (une ’bulle’ parcours le tableau et échange son contenu avec un élément approprié).

Le tri de Donald Shell est une amélioration du tri par insertion, cependant son efficacité dépend du nombre d’élément et de l’ordre du tableau de départ (le désordre en fait).

Le plus lent de tous (rassurez-vous la vidéo est accélérée) le tri par recherche du minimum, cherche la valeur la plus petite du tableau et la place en début, puis recommence avec le sous-tableau constitué des n-1 éléments restants... le problème, c’est qu’il ne se souvient pas à chaque étape des autres valeurs minima.

Le plus efficace : le tri rapide. Difficile à expliquer en quelques mots, mais faites bien attention aux chapeaux ils représentent des pointeurs sur le tableau. De plus, cet algorithme est récursif, ce qui explique que les danseurs se divisent en petits groupes. On applique à chaque groupe le tri, chaque sous-tableau trié est lui-même trié par rapport à l’ensemble.

Le tri par fusion lui aussi récursif, se base sur l’idée qu’il est facile de trier deux éléments. Il décompose son tableau en sous-tableaux de deux éléments, puis fusionne les résultats.

Vous pouvez tous les voir sur la chaîne Youtube Algorythmics’s.


Agenda

<<

2017

 

<<

Octobre

 

Aujourd’hui

LuMaMeJeVeSaDi
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345
Aucun évènement à venir les 6 prochains mois

Statistiques

Dernière mise à jour

vendredi 20 octobre 2017

Publication

1692 Articles
60 Albums photo
Aucune brève
29 Sites Web
88 Auteurs

Visites

9 aujourd’hui
562 hier
1452002 depuis le début
3 visiteurs actuellement connectés