Algorithmes classiques de tri
Il s'agit de trier une suite de "boules", d'objets ou une
suite de nombres dont les masses ou valeurs numériques sont 'cachées'.
Ces masses ou valeurs numériques sont visibles ici pour mieux
comprendre la suite des opérations.
Le seul outil est une balance de Roberval ou un simple test de comparaison,
permettant de comparer deux items.
Cela revient donc à ranger une liste de nombres avec comme seul
outil la comparaison de deux nombres.
Le
tri Insertion
Cette méthode est aussi appelée tri du "joueur de
cartes" car elle reproduit la méthode de classement des
cartes à jouer.
Lorsque des boules sont classées à gauche jusqu'au rang
j-1, la nouvelle boule de rang j est alors comparée à
toutes les
boules déjà triées et lorsqu'on trouve deux boules
entre lesquelles elle est comprise elle est alors insérée
à l'endroit correspondant.
On note que pour une liste de n éléments, ce tri nécessite
au maximum (n-1)+(n-2)+... +1=n(n-1)/2 opérations.
Il n'est pas très rapide.
Et... ainsi de suite.
ANIMATION
- CHOISIR d'effectuer une ANIMATION pour comprendre
ou de multiples EXPÉRIENCES, puis cliquer LANCER.
Ensuite :
- CHOISIR la longueur de la liste à trier.
Si EXPÉRIENCES ==> indiquer le nombre
de simulations à faire.
Si ANIMATION
- CHOISIR les données soi-même en les entrant
au clavier ou bien aléatoirement.
- CHOISIR le mode MANUEL ou le mode AUTOmatique.
En mode manuel, on avance pas à pas
en cliquant le bouton fléché.
En mode AUTO, le classement
se déroule automatiquement pas à pas.
On peut STOPPER pour observation avec le bouton
PAUSE.
On POURSUIT ensuite avec le bouton fléché.
- Lancer en cliquant le bouton GO.
CLIQUER
|