Premiers pas en JavaScript
30.2 arrays : algorithmes de tri
cuy copyleft
  See You Why?  

 

test tableaux join pop (29.9) | | exercices tri tableaux (30.?)

Contenu

 

 

I. La méthode sort()

voir <<<séquence précédente

 

 

II. Les algorithmes de tri

Il existe de nombreux algotithmes de tri. La suite de ce chapitre est une approche algorithmique de l'informatique, pas indispensable pour 'bidouiller' en programmation (dont le javascript). Cependant, comme un minimum de connaissance de la mécanique aide à mieux maitriser la conduite d'un véhicule, une bonne approche de l'algorithmique favorisera une programmation efficace.

Selon les fonctions mises en place pour ces tris, les algorithmes seront plus ou moins dévoreurs de capacité de votre ordinateur. Nous essaierons d'analyser cette gourmandise de chaque méthode (ce que d'aucuns appellent complexité du code).

On songera aussi à créer un tableau d'un nombre aléatoire (mais choisi par l'internaute) de valeurs aléatoirement choisies pour que le lecteur puisse lui-même tester et comparer la complexité des algorithmes choisis.

function creer_tabl() {
   <p>Entrez le nombre d'éléments que vous voulez générer dans le tableau à trier : </p>
   <input id="demande" value=""> </input><button id="lancer" type="button" onclick="creer()">Lancez</button>
}

Encore faut-il générer la fonction qui créera un tableau de valeurs aléatoires, sans qu'il n'y ait trop de doublons, en autorisant des valeurs manquantes dans la liste :

function creer() {
   nombre = document.getElementById("demande").value;
   t=[];
   for (var i=0;i<=nombre-1;i++) {
      //tire un nombre entier au hasard plus petit ou égal à nombre
      //Math.floor donne la partie entière
      // Math.random() donne une nombre au hasard entre 0 et 1 non compris
      value=Math.floor(Math.random()*nombre);
      t.push(value);
   }
   document.getElementById("tableaualeatoire").innerHTML = t.join(" ");
}

 

Nous aborderons ensuite successivement :

 

A. le tri par sélection

Soit à trier la liste suivante : 7, 3, 4, 0, 2, 1, 6, 5.

le principe du tri par sélection

Le principe est de :

* rechercher le plus petit élément [ou le plus grand] de la liste reçue (non triée) ;

* l'échanger avec le premier élément de la liste [ou le dernier] ;

* recommencer avec la nouvelle liste des éléments non triés.

les �tapes du tri par sélection

7  3  4  0  2  1  6  5  je recherche le plus petit élément des éléments non triés
7  3  4  0  2  1  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  3  4  7  2  1  6  5  je recherche le plus petit élément des éléments non triés
0  3  4  7  2  1  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  4  7  2 3  6  5  je recherche le plus petit élément des éléments non triés
0  1  4  7  2 3  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  7  4  3  6  5  je recherche le plus petit élément des éléments non triés
0  1  2  7  4  3  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  3  4  7  6  5  je recherche le plus petit élément des éléments non triés
0  1  2  3  4  7  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  3  4  7  6  5  je recherche le plus petit élément des éléments non triés
0  1  2  3  4  7  6  5  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  3  4  5  6  7  je recherche le plus petit élément des éléments non triés
0  1  2  3  4  5  6  7  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  3  4  5  6  7  je recherche le plus petit élément des éléments non triés
0  1  2  3  4  5  6  7  je l'échange avec le premier élément des éléments non triés
et le retire de la liste des éléments non triés
0  1  2  3  4  5  6  7   
�
 

Le lecteur attentif constatera donc que la fonction trier_selection ne comporte que deux sous-programmes :
* rechercher le plus petit élément d'une liste non triée ;
* échanger un élément avec un autre de la liste (ou retirer d'une liste à trier et placer dans une liste triée).

les routines JS du tri par sélection

Pour rechercher le plus petit élément d'une liste ou un tableau,

* je crée une fonction chercher_min() ;
* je lui passe un paramètre arr qui sera le tableau ou array à trier ;
* je détermine long la longueur ou nombre d'éléments de ce tableau ;
* je considère (provisoirement) le premier élément comme le plus petit du tableau mini ;
* pour chaque élément suivant de la liste :
   • si cet élément est plus petit que l'élément mini, alors :
      + cet élément est à considérer comme le nouvel élément le plus petit du tableau mini ;
* en fin de parcours des éléments de la liste, l'élément mini est le plus petit de la liste.

En JS on écrira :

function chercher_min(arr) {
   var long = arr.length;
   var mini = arr[0];
   for (j = 1; j<long; j++) {
      if (arr[j]<mini) {
         mini = arr[j];
      }
   }
   return mini;
}

Pour échanger deux éléments de place :

* je crée une fonction echanger_elt() ;
* je lui passe deux paramètres un et deux, à savoir les éléments à changer de place ;
* je place le premier élément un dans une variable provisoire provi ;
* je place le deuxième deux à la place du premier un ;
* Je place le premier élément placé provisoirement dans provi et le mets dans la variable deux.

En JS j'écrirai :

function echanger_elt(un, deux) {
   provi = un;
   un = deux;
   deux = provi;
}

 

VIII. Exercices relatifs aux tris de tableaux

voir suite >>>

 

 

test tableaux join pop (29.9) | | exercices tri tableaux (30.8)