|
LOGIQUE
DE TRI en
inform
|
|
||
FIFO
first in first out Premier entré, premier sorti. Comme la pile
de paquets de chewing-gum dans les distributeurs. |
LIFO last in first out Dernier entré, premier sorti. Comme la pile de
serviettes dans votre armoire. |
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Explication du processus (voir illustrations plus bas) Étape 1 – Opération 1: Trouver la valeur la plus petite; Opération 2: La mémoriser; Dans la pile, la cellule devient
vacante. La cellule de tête à gauche devient
vacante. La valeur la plus petite se retrouve
ainsi en tête de pile, à gauche. Fin de l'étape 1. Étapes suivantes: Recommencer cette
procédure avec la nouvelle valeur la plus petite dans la pile; Fin lorsque la nouvelle valeur la
plus petite est dans la cellule à l'extrémité droite de la pile. Étape 1 – Détail des opérations
Toutes les étapes
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
On prend les deux premiers nombres. S’ils sont dans le bon ordre, on ne
change pas. Sinon, on inverse. On recommence avec 2e et
le 3e . Etc. En
chiffres rouges, les deux cellules analysées. En
jaune, les nombres bien placés. Cellules
en bleu: le parcours du nombre 3.
Il
y a beaucoup plus d’opérations que dans le cas du tri
classique, mais
l'algorithme est plus simple pour l’informatique. Observez
le nombre 3 qui se propage de la droite vers la gauche, comme
une " bulle " qui remonte à la surface (ici, vers la droite). |
|
||||||||||||||||||||||||||
Tri classique Le
nombre d'opérations à effectuer est proportionnel au carré de la quantité d'objets à trier. Pour 1000
fiches T = (103)²
t = 106
t |
Tri à bulles ou par petits paquets Le
nombre d'opérations à effectuer est proportionnel au produit du nombre
d'objets par son logarithme. Pour 1000
fiches T = 103 ln 1000 = 6, 9 103 t |
|||||||||||||||||||||||||
Comparaison
Référence: pages 84 et 85 du livre cité Note Malgré
la référence, cette comparaison ne tient pas par rapport au tableau
présenté par Wikipédia.
|
||||||||||||||||||||||||||
|
||
|
Commentaires Déclaration de la procédure ( en fait, une sorte de nouvelle
instruction) NN mémorise la liste N pour travail en interne et q en donne la
quantité d'éléments. Les deux boucles fonctionnent comme ceci:
La procédure retourne la liste NN triée. Fin de procédure Essais avec une liste quelconque et effet de tri sur cette liste. |
|
Voir Programmation
– Index
Tout programme de tri qui garantit une complexité de N log N est le meilleur. C'est prouvé. En
moyenne l'algorithme de tri rapide (quicksort) réalise cette performance. Néanmoins, pour certains types particuliers de données, il
peut exister de meilleurs algorithmes que ceux-ci. Le tri à bulles, simple à implémenter, est un algorithme
lent. Vous trouverez la comparaison entre divers algorithme sur la
page Wikipédia. |
Suite |
|
Voir |
|
Espèce de
Trochoïde
– Luc de Brabandere et Christophe Ribesse – Dunod – 2006: Florilège de 50
idées mathématiques expliquées au profane. Superbe! |
|
Sites |
|
Cette page |