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

<<

2016

 

<<

Décembre

 

Aujourd’hui

LuMaMeJeVeSaDi
2829301234
567891011
12131415161718
19202122232425
2627282930311
Aucun évènement à venir les 6 prochains mois

Statistiques

Dernière mise à jour

vendredi 9 décembre 2016

Publication

1519 Articles
60 Albums photo
Aucune brève
29 Sites Web
85 Auteurs

Visites

56 aujourd’hui
755 hier
1203989 depuis le début
15 visiteurs actuellement connectés