Leçon 6

Traitements des tableaux en Javascript

Dans le répertoire javascript créez un dossier cours6. Il contiendra tous les fichiers de cette leçon.
Sur l'éditeur Brackets allez dans Fichier, ouvrez un dossier et sélestionnez le dossier cours6. Le nom du dossier s'affiche à gauche.
A l'aide d'un clic droit de la souris sur le nom du dossier, créez un dossier js puis un dossier html.

Deux méthodes de tri

Méthode simple

Écrire un programme tri_simple.js permettant de trier un tableau, c’est-à-dire ordonner les valeurs des éléments dans l’ordre croissant. On utilisera la méthode suivante:

  1. On recherche la plus petite valeur du tableau et on la place au rang 0
  2. On recommence le même travail au rang 1, 2 et ainsi de suite jusqu'à ce que le tableau soit totalement trié.

Un seul tableau est utilisé lors de ce tri. On supposera le tableau déjà initialisé.
Exemple :

  1. L = [30,10,1,5,20,7,7] On permute 30 premier élément de la liste non ordonnée et 1 minimum de cette liste
  2. L = [1, 10, 30, 5, 20, 7, 7] On permute 10 premier élément de la liste non ordonnée et 5 minimum de cette liste.
  3. L =[1, 5, 30, 10, 20, 7, 7] On permute 30 premier élément de la liste non ordonnée et 7 minimum de cette liste
  4. L =[1, 5, 7, 10, 20, 30, 7] On permute 10 premier élément de la liste non ordonnée et 7 minimum de cette liste
  5. L =[1, 5, 7, 7, 20, 30, 10] On permute 20 premier élément de la liste non ordonnée et 10 minimum de cette liste
  6. L = [1, 5, 7, 7, 10, 30,20] On permute 30 premier élément de la liste non ordonnée et 20 minimum de cette liste
  7. L = [1, 5, 7, 7, 10, 20, 30]

Aide : Algorithme

Méthode du tri à bulle

Cette méthode consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide. On compare deux élément successifs et on les permute éventuellement. Le tri est fini lorsque sur un passage aucune permutation a été réalisée. Pour cela on pourra utiliser une variable booléenne tri qui prend la valeur false dès que l'on fait une permutation.
Exemple :

1er passage 2ième passage 3ième passage 4ième passage
[30,10,1,5,20,7,7]
[10,30,1,5,20,7,7]
[10,1,30,5,20,7,7]
[10,1,5,30,20,7,7]
[10,1,5,20,30,7,7]
[10,1,5,20,7,30,7]
[10,1,5,20,7,7,30]
[10,1,5,20,7,7,30]
[1,10,5,20,7,7,30]
[1,5,10,20,7,7,30]
[1,5,10,7,20,7,30]
[1,5,10,7,7,20,30]
 
 
[1,5,10,7,7,20,30]
[1,5,7,10,7,20,30]
[1,5,7,7,10,20,30]
 
 
 
 
[1,5,7,7,10,20,30]
 
 
 
 
 
 

Écrire un programme tri_bulle.js qui applique cette méthode

Aide : Algorithme

Recherche d'un élément dans une liste triée

Recherche simple

Écrire un programme recherche.js permettant de retrouver une valeur dans une liste triée, cette valeur sera saisie au clavier.
On indiquera en résultat, la position de la valeur dans la liste. La valeur recherchée peut aussi être absente de la liste.


Aide : Algorithme

Recherche par dichotomie.

Exemples : L=[1,5,7,7,20,30]

  1. On cherche 5 $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2 &&&\\ &~~& T[2]=7 &&&\\ & & 5 < 7 &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline inf=0 & sup=milieu-1=1&&&\\ ~milieu=\dfrac{0+1}{2}=0& & &&&\\ T[0]=1 &&&&&\\ 5>1 && &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & inf=milieu+1=1 &&&\\ & sup=1&&&\\ &~milieu=\dfrac{1+1}{2}=1 & &&&\\ &T[1]=5 &&&&\\ \hline \end{array}$$
  2. On cherche 30. $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2& &&\\ && T[2]=7& &&\\ & & 30>7 & &&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & &&inf=milieu+1=3 &milieu=\dfrac{3+5}{2}=4&sup=5\\ & & &&&\\ & &&&T[4]=20&\\ & & &&30>20&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & &&& &inf=milieu+1=5\\ & & &&&~milieu=\dfrac{5+5}{2}=5\\ &&&&&T[5]=30 \\ \hline \end{array}$$
  3. On cherche 2 $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2 &&&\\ &~~& T[2]=7 &&&\\ & & 2 < 7 &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline inf=0 & sup=milieu-1=1&&&\\ ~milieu=\dfrac{0+1}{2}=0& & &&&\\ T[0]=1 &&&&&\\ 2>1 && &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & inf=milieu+1=1 &&&\\ &~milieu=\dfrac{1+1}{2}=1 & &&&\\ &T[1]=5 &&&&\\ &2<5 &&&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline sup=milieu-1=0&inf&&&&\\ \hline \end{array}$$

Aide : Algorithme