Le Tri

Le tri est important afin de faciliter l'accès aux infos et pour comprendre le fonctionnement de l'ordi.

Pour commencer il faut savoir que toute informations se situe dans une case mémoire appelé variable, or cette case ne peut comporter qu'une seule information à la fois et une seule opération est possible, il faut donc tous organiser pour perdre le moins de temps possible et faciliter la tâche à l'ordinateur.

Maintenant voyons les différentes méthodes de trie.

Le Tri à bulle

Le tri à bulle consiste à un déplacement dans une liste/tableau où l'ordi va comparer 2 info à la fois et les échanger si besoin (exemple: une liste 4/5/3/7, l'ordi va effectuer le déplacement suivant pour obtenir une liste croissant: 4-5: 4<5 donc 4/5/3/7. Puis 5-3: 5>3 donc 4/3/5/7 et enfin 5-7: 5<7 donc 4/3/1/5/7. A la fin l'ordi va revenir au début et répéter cette boucle jusqu'à qu'il n'y plus de changement à faire.

Le Tri par sélection/insertion

Ce trie consiste à rajouter les données une à une en les classant.

Pour comprendre imaginons que l'on doit classer 10 carte nommé A/B/C/D/E/F/G/H/I/J, que chacune de ces cartes ont une valeur caché (ici les valeur seront: 5/8/6/4/9/10/2/3/1/7) et que pour les triés on ne peut poser qu'une seule question: est-ce que ... est >/< que ... .

Commençons donc par le début comparons A et B, 5<8 donc la liste est A/B maintenant ajoutons C, pour cela il faut le comparer à A et B l'une après l'autre ce qui donne C>A et C<B donc la liste est A/C/B. Jusqu'à là c'est simple.

      Mais à partir de la quatrième carte on peut optimiser le nombre de question. En effet si on compare D au milieu de la liste actuelle on élimine une question et il ne reste plus qu'une seule: comparons donc D à C (le milieu), D<C donc on sait que D est forcément inférieur à B vue que C<B, maintenant dernière comparaisons: D et A: D<A, la liste est donc D/A/C/B.

     Pour ajouter E nous allons procéder à la même technique sauf que nous n'avons pas de milieu précis, il faut donc utiliser une des cartes les plus proches de ce milieu (et avoir de la chance pour l'optimisation). Donc comparons E à C, E<C, maintenant comparons E à B (seule valeur restante), E>B donc la liste est D/A/C/B/E.

     Même principe pour les cartes F et G, la liste à la fin des comparaisons est G/D/A/C/B/E/F.

     Maintenant pour placer la 8ème carte, c'est la même technique qu'avant sauf que l'on va comparer la carte aux moitié des moitiés restante. Dans notre cas C est le milieu, la première comparaison est donc H et C qui donne H<C, il nous reste donc trois carte à comparer comme quand on a placer D c'est à dire qu'il faut comparer H au milieu (ici :D) ce qui donne H<D, Il nous reste plus q'une carte à comparer: H>G. Notre liste est donc G/H/D/A/C/B/E/F.

    Le processus est le même pour toute les cartes suivante: 

          Pour I:  I-A= I<A,  I-H= I<H,  I-G=I<G donc I/G/H/D/A/C/B/E/F.

          Pour J:  J-A= J>A,  J-B= J<B,  J-C=J>C donc I/G/H/D/A/C/B/E/F.