Accueil Casino argent reel Meilleur casino Nouveaux casinos Live casino
vk ok fb

 
 

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 algorithmes de tri.

"Algo...", comment ? Algorithme ou si vous préférez un processus, un procédé, une règle à suivre, une recette... WikiPedia précise "Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions élémentaires permettant de résoudre un problème." Et les auteurs de ce dictionnaire, comme beaucoup d'enseignants, illustrent leur propos par l'exemple des recettes de cuisine qui précisent (1) les entrées (ingrédients, matériel utilisé...), (2) instructions élémentaires simples, dont l'exécution amène au résultat voulu et (3) la sortie (le plat préparé).

Nombreuses sont les recettes qui ne répondent pas rigoureusement à la définition de l'algorithme. Je ne suis pas un chef coq, mais je sais faire les omelettes, il suffit de : "Casser vos œufs dans une sauteuse dans laquelle vous aurez mis votre beurre à fondre..." :

Ce que j 'ai fait... Mes commentaires...
casser mes œufs en revenant du poulailler, j'avais mis mes œufs en poche et Médor a sauté de joie en me voyant revenir... mes œufs sont cassés, bon départ pour suivre la recette...
dans une sauteuse qu'est-ce qu'une sauteuse ?
Après recherche au dictionnaire, je suis allé au magasin m'acheter le matériel nécessaire et j'ai cassé mes œufs (des nouveaux, bien sûr... mais combien ?) dans ma poêle...
dans laquelle vous aurez mis votre beurre Zut ! Ils auraient pu me le dire plus tôt...
Je recommence et mets mon beurre (quantité ?) dans ma poêle et je casse mes œufs... c'est presque gagné !
à fondre Malheureusement, une motte de beurre posée dans ma sauteuse n'a pas aidé... alors, après deux heures sous le soleil dans ma serre (en Belgique, ça n'arrive pas souvent...), avec ma poêle et le beurre (fondant), j'ai cassé mes œufs dans ma poêle... je pouvais continuer à lire ma recette...

Le lecteur aura vite compris qu'il n'est pas facile d'énoncer correctement une suite finie et ordonnée d'opérations élémentaires visant à atteindre un résultat.

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

Nombreux sont les parents et enseignants qui estiment que smartphones et autres ordis ne sont que des moyens de perdre son temps... Et pourquoi ne pas découvrir YouTube comme une occasion d'apprendre. Cette illustration visualise le processus de tri par sélection : on recherche le plus petit élément de la liste non triée et on place cet élément en queue de la liste triée... et on apprend l'anglais :

 

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

le principe du tri par sélection

Le principe du tri par sélection 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;
}

Un petit essai de ce tri par sélection ?

Exemple de tri par sélection

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="Content-Type" cont  ent="text/html; charset=iso-8859-1" />
  <title>CUY jvs tri selection</title>
</head>

<body>
  <p>Combien d &eacute;l&eacute;ments votre tableau doit-il avoir ? <br />
  <input id="nbr" value=""> </input><button id="creer" type="button" onclick="creer_tab()">Cr&eacute;ez le tableau</button>
  <p>&nbsp;</p>
  <div>Voici le tableau des n éléments: <br />
  <span id="affich">&nbsp;</span></div>
  <p>&nbsp;</p>

<h1>Tri par sélection</h1>
  <div><button id="tri_select" type="button" onclick="trier_select()">Triez</button></div>
  <div><b>Nombre total de permutations réalisées : </b><br />
  <span id="nbr_permut_select">&nbsp;</span><br />
  <b>Détail des étapes :</b><br />
  <span id="etap_select">&nbsp;</span><br />
  <b>Durée du tri selection :</b><br />
  <span id="duree_tri_select">&nbsp;</span> ms
  <p>

<script type="text/javascript">
  var aArr = [];
  var aCop = [];
  function creer_tab() {
    nbre = document.getElementById("nbr").value;
    aArr = [];
    for (i=0;i<nbre;i++) {
      it = Math.floor(Math.random()*nbre*1.1); 
      aArr.push(it);
    }
    document.getElementById("affich").innerHTML = aArr.join(" ; ");
  }

  function trier_select() {
    nudepart = (new Date()).getTime();
    var nbre_permut_select=0;
    var longu = aArr.length;
    var temp;
    for (var i=0;i<longu;i++){
      aCop[i]=aArr[i];
      //pour conserver le tableau aArr et travailer sur sa copie aCop
    }

    for (i=0;i<(longu-1);i++) {
      indic_min = i;
      //le premier est provisoirement le plus petit
      for (j=i+1;j<longu;j++) {
        //parmi les suivants non triés
        if (aCop[j] < aCop[indic_min]) {
        //s'il y en a un plus petit, il devient le nouveau minimum
          indic_min = j;
        }
      }
      if (indic_min != i) {
      //si le plus petit n'est pas le premier, je les permute
        temp = aCop[i];
        aCop[i] = aCop[indic_min];
        aCop[indic_min] = temp;
        nbre_permut_select++;
      }
      document.getElementById("etap_select").innerHTML += i + " == " + aCop.join(" ; ") + "<BR>";
      document.getElementById("nbr_permut_select").innerHTML = nbre_permut_select;
    }
    nufin = (new Date()).getTime();
    document.getElementById("duree_tri_select").innerHTML = nufin - nudepart;
  }

</script>
</body>
</html>

 

 

B. le tri par insertion

Soit toujours à trier la même liste : 7, 3, 4, 0, 2, 1, 6, 5.

le principe du tri par insertion

Tout-à-fait comparable au joueur de cartes qui ramasse ses cartes après distribution, le principe est de :

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

* prendre le premier élément de la liste restante non triée [ou le dernier] ;

* comparer cet élément avec chacun de la liste déjà triée et
   insérer cet élément à sa place dans la liste triée ;

* recommencer avec la nouvelle liste des éléments non triés (voir étape 2).

 

les étapes du tri par insertion

7  3  4  0  2  1  6  5  je considère le premier élément des éléments non triés comme le plus petit des éléments triés
7  3  4  0  2  1  6  5  je prends le premier élément des éléments non triés
7  3  4  0  2  1  6  5  je le compare avec chaque élément de la liste triée
7     4  0  2  1  6  5  et l'insère à sa place
3  7  4  0  2  1  6  5  je prends le premier élément des éléments non triés
3  7  4  0  2  1  6  5  je le compare avec chaque élément de la liste triée
3  7    0  2  1  6  5  et l'insère à sa place
3  4  7  0  2  1  6  5  je prends le premier élément des éléments non triés
3  4  7  0  2  1  6  5  je le compare avec chaque élément de la liste triée
3  4  7    2  1  6  5  et l'insère à sa place
0  3  4  7  2  1  6  5  je prends le premier élément des éléments non triés
0  3  4  7  2  1  6  5  je le compare avec chaque élément de la liste triée
0  3  4  7    1  6  5  et l'insère à sa place
0  2  3  4  7  1  6  5  je prends le premier élément des éléments non triés
0  2  3  4  7  1  6  5  je le compare avec chaque élément de la liste triée
0  2  3  4  7    6  5  et l'insère à sa place
0  1  2  3  4  7  6  5  je prends le premier élément des éléments non triés
0  1  2  3  4  7  6  5  je le compare avec chaque élément de la liste triée
0  1  2  3  4  7    5  et l'insère à sa place
0  1  2  3  4  6  7  5  je prends le premier élément des éléments non triés
0  1  2  3  4  6  7  5  je le compare avec chaque élément de la liste triée
0  1  2  3  4  6  7    et l'insère à sa place
0  1  2  3  4  5  6  7   

Le lecteur imaginera facilement, les cartes vertes dans la main gauche, les blanches dans la main droite et la brune à placer dans la main gauche...

Pour chaque étape, nous admettrons que :
* le nombre total d'éléments du tableau est n ;
* le nombre d'éléments déjà triés du tableau est i ;
* le nouvel élément à insérer est le i+1e ;

view-source:http://isnangellier.alwaysdata.net/tris_bulle_insertion_selection_fusion.html

les routines JS du tri par insertion

Pour ... un tableau,

* je crée une fonction che

 

Un essai de ce tri par insertion ici aussi ?

Exemple de tri par insertion

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
  <title>CUY jvs tri insertion</title>
</head>

<body>
  <p><b>Combien d &eacute;l&eacute;ments votre tableau doit-il avoir ? </b><br />
  <input id="nbr" value=""> </input><button id="creer" type="button" onclick="creer_tab()">Cr&eacute;ez le tableau</button>
  <p>&nbsp;</p>
  <div><b>Voici le tableau des n éléments: </b><br />
  <span id="affich">&nbsp</span></div>
  <div><b>Message : </b><br />
  <span id="message">&nbsp;</span></div>
  <p>&nbsp;</p>

<h1>Tri par insertion</h1>
  <div><button id="tri_insert" type="button" onclick="trier_insert()">Triez</button></div>
  <div><b>Nombre total de permutations réalisées : </b><br />
  <span id="nbr_permut_insert"> </span><br />
  <b>D&eacute;tail des &eacute;tapes </b><br />
  <span id="etap_insert"> </span><br />
  <b>Durée du tri insertion :</b><br>
  <span id="duree_tri_insert"> </span> ms</div>
  <p>

<script type="text/javascript">
  var aArr = [];
  var aCop = [];
  function creer_tab() {
    nbre = document.getElementById("nbr").value;
    aArr = [];
    for (i=0;i<nbre;i++) {
      it = Math.floor(Math.random()*nbre*1.1);
      aArr.push(it);
    }
    document.getElementById("affich").innerHTML = aArr.join(" ; ");
  }

function trier_insert() {
  nudepart_insert = (new Date()).getTime();
  var nbre_permut_insert=0;
  var permut_preced = 0;
  var longu = aArr.length;
  document.getElementById("etap_insert").innerHTML = " ";
  aCop = [];
  for (var i=0;i<longu;i++){
    aCop[i]=aArr[i];
    //pour conserver le tableau aArr et travailer sur sa copie aCop
  }
  document.getElementById("message").innerHTML ="copie finie";
  for (i=1;i<longu;i++) {
  //pour chaque élément du tableau
    j=i;
    permut_preced = nbre_permut_insert;
    //à partir du deuxième
    while (aCop[j-1]>aCop[j] && j>0) {
      //tant que du j ième au 1er, (du 1er non trié dans la liste des triés,
      //tu les permutes
      temp=aCop[j-1];
      aCop[j-1]=aCop[j];
      aCop[j]=temp;
      j--;
      nbre_permut_insert++;
    }
    document.getElementById("etap_insert").innerHTML += i + " == " + aCop.join(" ; ") + "<BR>";
    document.getElementById("etap_insert").innerHTML += i + " == nombre de permutations == <b>" + (nbre_permut_insert - permut_preced) + "</b><BR>";
    document.getElementById("nbr_permut_insert").innerHTML = nbre_permut_insert;
  }
  nufin_insert = (new Date()).getTime();
  document.getElementById("duree_tri_insert").innerHTML = nufin_insert - nudepart_insert;
}

</script>

</body>
</html>

 

C. le tri à bulles

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

le principe du tri à bulles

Le principe du tri à bulles est de :

* parcourir le tableau et comparer des éléments successifs ;

* si deux éléments successifs ne sont pas dans l'ordre croissant, on les échange ;

* arrivé à la fin du tableau, on recommence le parcours par paires successives ;

* on arrête lorsqu'il n'y a aucun échange effectué dans un parcours.

Une illustration :

Une autre illustration (par Lego) :

 

 

les étapes du tri à bulles

7  3  4  0  2  1  6  5  je considère la première paire d'éléments non triés
7  3  4  0  2  1  6  5  non croissants, donc j'échange
3  7  4  0  2  1  6  5  je considère la paire suivante d'éléments non triés
3  7  4  0  2  1  6  5  non croissants, donc j'échange
3  4  7  0  2  1  6  5  je considère la paire suivante d'éléments non triés
3  4  7  0  2  1  6  5  non croissants, donc j'échange
3  4  0  7  2  1  6  5  je considère la paire suivante d'éléments non triés
3  4  0  7  2  1  6  5  non croissants, donc j'échange
3  4  0  2  7  1  6  5  je considère la paire suivante d'éléments non triés
3  4  0  2  7  1  6  5  non croissants, donc j'échange
3  4  0  2  1  7  6  5  je considère la paire suivante d'éléments non triés
3  4  0  2  1  7  6  5  non croissants, donc j'échange
3  4  0  2  1  6  7  5  je considère la paire suivante d'éléments non triés
3  4  0  2  1  6  7  5  non croissants, donc j'échange
3  4  0  2  1  6  5  7  il n'y a plus de paire,
mais j'ai dû faire des échanges,
1er passage : 1 élt bien placé en queue (7)
je recommence,
je considère la première paire d'éléments non triés
3  4  0  2  1  6  5  7  croissants, donc pas d'échange
3  4  0  2  1  6  5  7  je considère la paire suivante d'éléments non triés
3  0  4  2  1  6  5  7  non croissants, donc j'échange
3  0  4  2  1  6  5  7  je considère la paire suivante d'éléments non triés
3  0  2  4  1  6  5  7  non croissants, donc j'échange
3  0  2  4  1  6  5  7  je considère la paire suivante d'éléments non triés
3  0  2  1  4  6  5  7  non croissants, donc j'échange
3  0  2  1  4  6  5  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
3  0  2  1  4  6  5  7  non croissants, donc j'échange
3  0  2  1  4  5  6  7  il n'y a plus de paire non triée,
mais j'ai dû faire des échanges,
2e passage : 2 élts bien placés en queue (6 et 7)
je recommence,
je considère la première paire d'éléments non triés
3  0  2  1  4  5  6  7  non croissants, donc j'échange
0  3  2  1  4  5  6  7  je considère la paire suivante d'éléments non triés
0  3  2  1  4  5  6  7  non croissants, donc j'échange
0  2  3  1  4  5  6  7  je considère la paire suivante d'éléments non triés
0  2  3  1  4  5  6  7  non croissants, donc j'échange
0  2  1  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  2  1  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  2  1  3  4  5  6  7  il n'y a plus de paire non triée,
mais j'ai dû faire des échanges,
3e passage : 3 élts bien placés en queue (5, 6 et 7)
je recommence,
0  2  1  3  4  5  6  7  je considère la première paire d'éléments non triés
croissants, donc pas d'échange
0  2  1  3  4  5  6  7  je considère la paire suivante d'éléments non triés
non croissants, donc j'échange
0  1  2  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  1  2  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  1  2  3  4  5  6  7  il n'y a plus de paire non triée,
mais j'ai dû faire un seul échange,
4e pass. : 4 élts bien placés en queue (4, 5, 6 et 7)
je recommence,
je considère la première paire d'éléments non triés
croissants, donc pas d'échange
0  1  2  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  1  2  3  4  5  6  7  je considère la paire suivante d'éléments non triés
croissants, donc pas d'échange
0  1  2  3  4  5  6  7  il n'y a plus de paire non triée,
et pas un seul échange dans ce passage,
FINI

Le lecteur attentif aura remarqué qu'à chaque passage dans la boucle, il y a un élément en moins à envisager : celui qui a été emmené en dernière position, c'est-à-dire le plus grand qui a été emmener en fin de série. Et si ce lecteur parvient à soutenir son attention jusqu'au bout, il remarquera que ce racourcissement de boucle en boucle n'a pas été mis en oeuvre dans le propgramme proposé...

Le lecteur attentif (s'il l'est encore ;o) ) aura aussi observé que si aucun échange n'a été effectué lors du parcours d'une boucle, c'est que tous les éléments sont correctement placés et qu'il n'y a plus lieu de faire de nouveaux passages (pour déterminer que le plus grand est bien placé) pour s'assurer que tous soient bien ordonnés.
Si ce même lecteur est aussi attentif au code qui suit, il aura remarqué qu'au départ de la boucle, la variable logique arreter est mise à true et que sa valeur logique ne sera mise à false que si une permutation ou échange d'éléments a lieu, donc que ce raccourci est utilisé dans le code ci-après.

les routines JS du tri à bulles

Pour ... un tableau,

* je crée une fonction che

 

Et pourquoi pas un essai de ce tri à bulles ?
 

Exemple de tri à bulles

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
   <title>CUY jvs tri à bulles</title>
</head>

<body>
  <p><b>Combien d &eacute;l&eacute;ments votre tableau doit-il avoir ? </b><br />
  <input id="nbr" value=""> </input><button id="creer" type="button" onclick="creer_tab()">Cr&eacute;ez le tableau</button>
  <p>&nbsp;</p>
  <div><b>Voici le tableau des n éléments: </b><br />
  <span id="affich">&nbsp</span></div>
  <div><b>Message : </b><br />
  <span id="message">&nbsp;</span></div>
  <p>&nbsp;</p>

<h1>Tri à bulles</h1>
  <div><button id="tri_bull" type="button" onclick="trier_bull()">Triez</button></div>
  <div><b>Nombre total de permutations réalisées : </b><br />
  <span id="nbr_permut_bull"> </span><br />
  <b>D&eacute;tail des &eacute;tapes </b><br />
  <span id="etap_bull"> </span><br />
  <b>Durée du tri insertion :</b><br>
  <span id="duree_tri_bull"> </span> ms</div>
  <p>

<script type="text/javascript">
  var aArr = [];
  var aCop = [];
function creer_tab() {
  nbre = document.getElementById("nbr").value;
  aArr = [];
  for (i=0;i<nbre;i++) {
     it = Math.floor(Math.random()*nbre*1.1);
     aArr.push(it);
  }
  document.getElementById("affich").innerHTML = aArr.join(" ; ");
}
function trier_bull() {
  nudepart_bull = (new Date()).getTime();
  var nbre_permut_bull=0;
  var permut_preced = 0;
  var longu = aArr.length;
  document.getElementById("etap_bull").innerHTML = " ";
  aCop = [];
  for (var i=0;i<longu;i++){
     aCop[i]=aArr[i];
     //pour conserver le tableau aArr et travailer sur sa copie aCop
  }
document.getElementById("message").innerHTML ="copie finie";
for (i=0;i<(longu-1);i++) {
//pour chaque élément du tableau
  arreter = true;
  //on remet l'arret à l'honneur (sauf si permutation dans la boucle)
  permut_preced = nbre_permut_bull;
  //à partir du suivant jusqu'au dernier
  for (j=0;j<longu;j++) {
     if (aCop[j+1]<aCop[j]) {
     //si l'élément j est plus grand que le suivant
     //tu les permutes
        temp=aCop[j];
        aCop[j]=aCop[j+1];
        aCop[j+1]=temp;
        nbre_permut_bull++;
        arreter = false;
        // une permutation dans la boucle... donc on doit recommencer une boucle
     }
     document.getElementById("etap_bull").innerHTML += i + "-" + j + " == " + aCop.join(" ; ") + ((arreter==false)?" = on devra continuer":" = arrêt possible") + "<BR>";
  }
  document.getElementById("etap_bull").innerHTML += i + " == nombre de permutations == <b>" + (nbre_permut_bull - permut_preced) + "</b><BR>";
  document.getElementById("nbr_permut_bull").innerHTML = nbre_permut_bull;
  if (arreter==true) {
     break;
  }
}
nufin_bull = (new Date()).getTime();
document.getElementById("duree_tri_bull").innerHTML = nufin_bull - nudepart_bull;
}

</script>

</body>
</html>

 

 

 

VIII. Exercices relatifs aux tris de tableaux

voir suite >>>

 

 

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