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)

 

 

Merci de votre visite à partir de :

Vous êtes sur :
https://cuy.be/cours/jvs/jvs_305_algo_tri.html

partager sur FaceBook...           consulter sur FaceBook...

 

copyleft
Des liens ne fonctionnent plus ?
Avez-vous des suggestions ?
des commentaires, des corrections, un encouragement... ?
Pour info : Non, il n'y a pas de version papier ou DOC, PDF, etc. de ces notes.


Envoyez-moi un E-Mail (cuy(point)w(at)skynet(point)be)
Attention (at) signifie @ et (point) signifie .

Accueil CUY = See you why?

Compteur gratuitEasyCounter     BelStat Monitored by BelStat - Your Site Counts
La 1 000 000e page a été visitée le 21 mai 2010.
La 2 000 000e page a été visitée ce 18 mars 2012, vers midi.
La 3 000 000e page a été visitée ce 7 janvier 2014 entre 18 h et 18 h 45,
La 4 000 000e page a été visitée ce 5 juin 2015 entre 15 h 49 et 15 h 52,
La 5 000 000e page a été visitée ce 29 aout 2017 après 23 h 30,
Et la 6 000 000e page visitée, trop tôt pour y penser ?
 
et, d'après BelStat, CUY est visité surtout en semaine, peu le weekend...
moins et irrégulièrement pendant les vacances :

visites sur 3 mois, de la mi octobre 2013 à la mi janvier 2014.
 
La 3 333 333e page visitée a eu lieu ce mardi 10 juin 2014, en début d'après midi...
La 3 666 666e page visitée a eu lieu ce dimanche 28 decembre 2014, vers 16 h...
Un tiers de million de pages visitées en 154 jours cela fait une moyenne de 2165 pages visitées par jour...
Deux tiers de million de pages visitées en 355 jours soit une moyenne de 1878 pages visitées par jour...
et seulement 1195 pages visitées quotidiennement pendant les vacances estivales
de la mi juin à la mi septembre 2014

Vous voulez lire quelques messages reçus ?
quelques encouragements ?
Cliquez ici

Fin septembre 2009, installation de ce compteur
qui ne compte chaque nouvel ordinateur visiteur qu'une seule fois
free counter
 
m-à-j du 22/11/2021 :
Depuis cette fin septembre 2009, parmi les 210 pays (sur 274 drapeaux connus) qui nous ont visité,
voici les 100 pays qui nous visitent le plus, 
Nos petits visiteurs, classés par date de visite, où un seul ordi nous a visité, sont :
199. Turkmenistan (TM May 10, 2017) ; 200. Lesotho (LS March 1, 2017) ;
201. Turks and Caicos Island (TC January 18, 2016) 
202. Cook Islands (CK September 19, 2015)  203. Faroe Islands (FO January 27, 2015) 
204. Virgin Islands American (VI November 12, 2014) ;
205. Belize (BZ September 29, 2014) ;206. Eswatini - Swaziland (SZ July 21, 2014) ;
207. Grenada (GD April 3, 2014) ; 208. Timor-Leste (TI March 29, 2014) ;
209. American Samoa (AS December 26, 2012) ; 210. Guyana (GY November 5, 2010).