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

 

<<

Janvier

>>

Aujourd’hui

LuMaMeJeVeSaDi
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

Sur le Web

13 janvier - Programme de colles Physique PCSI 2016-2017

9 janvier - Programme des colles de maths de PC

8 janvier - La naissance de l'informatique

7 janvier - A méditer...

Décembre 2016 - Premier Concours Blanc PCSI 2017

Décembre 2016 - Programme de Colles de SI

Décembre 2016 - Sujet de devoir libre PSI

Décembre 2016 - Les 10 km du canal en "famille" !

Décembre 2016 - Le champion des champions !

Novembre 2016 - Quiz de matheux à physicien : 2° question

Novembre 2016 - PC réorganisation de l'emploi du temps

Novembre 2016 - Statistiques d'intégration

Novembre 2016 - Résultats 2013-2016

Novembre 2016 - Programme de colles de chimie -PCSI

Novembre 2016 - Asymptotique ou parabolique ?

Novembre 2016 - Mais qu'entends-je ?

Novembre 2016 - Est-ce que monter est le contraire de descendre ?

Novembre 2016 - Changement d'heure

Novembre 2016 - Développement du déterminant : la formule qui manque à votre formulaire "Dunod"

Novembre 2016 - Voyage d'un électron

Novembre 2016 - Programme de colles de chimie -PC

Novembre 2016 - 10 km du canal - Venez défier vos profs !

Novembre 2016 - De la radioactivité

Octobre 2016 - Devoir maison n°3 - Chimie PCSI

Octobre 2016 - Prix Nobel de Chimie 2016

Octobre 2016 - Inscription complémentaire à l'Université de Bordeaux

Septembre 2016 - Tracé d'un binaire Solide Liquide à pression constante

Septembre 2016 - Colloscope PCSI

Septembre 2016 - Emploi du temps

Septembre 2016 - Magie : deux phases présentant un indice de réfraction quasi identique

Statistiques

Dernière mise à jour

jeudi 19 janvier 2017

Publication

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

Visites

1085 aujourd’hui
1279 hier
1237846 depuis le début
48 visiteurs actuellement connectés