tri

Trier sans sort()

Écrire un script js qui

génére un tableau A d'entiers au hasard,
ordonne les éléments (ordre croissant) dans le tableau A,
affiche le résultat.

Contrainte : l'usage de la méthode sort() est interdite.

Il existe de nombreuses façons de répondre à la demande. Vous pouvez effectuer une recherche sur le web avec les mots clefs "algorithme de tri" pour vous en convaincre.

La solution proposée ci-dessous est simple, bien que peu efficace du point de vue temps de calcul. Il s'agit du principe du tri par sélection. Vous pouvez lire cette page avant de retenter de répondre à l'exercice si vous n'y êtes pas parvenu. Lire ensuite le code proposé.

<!DOCTYPE html>
<html lang="fr">
    <head>
        <meta charset="utf-8">
        <title> tri  </title>
    </head>
    <body>
    
        <script>
        // on définit un tableau vide  :  
        let A = [];
        // on tire au hasard la longueur du tableau entre 5 et 20 :
        let longueur = Math.floor(Math.random() * 16) + 5;
        
        for(let i = 0; i < longueur; i++) {
        	// ajout d'un entier pris au hasard entre 0 et 199 : 
        	A.push( Math.floor(Math.random() * 200 )  );
        }
        
        document.write("Le tableau à trier  : " + A);
        document.write('<br>');
        document.write('<hr>');
        
         
        
        for(let i = 0; i < A.length; i += 1) {
        	//on recherche l'élément minimum parmi les éléments
        	// A[i], A[i+1], ..., A[A.length-1]
        	let mini = A[i];
        	let indiceDuMin = i;
        	for(let j = i+1; j < A.length; j +=1) {
        		if (A[j] < mini) {
        			mini = A[j];
        			indiceDuMin = j;
        		}
        	}
        	
        	// mise en mémoire de l'élément A[i]
        	let valeur = A[i];
        	
        	// on remplace A[i] par l'élément mini 
        	A[i] = mini;
        	// l'ancien emplacement de cet élément minimum 
        	// récupère la valeur de A[i] :
        	A[indiceDuMin] =  valeur; 
        }
         
        document.write("Le tableau  après tri : " + A);
        </script>
    </body>
</html>

Insertion d'un élément dans un tableau en ordre.

Écrire un script js qui

génére un tableau d'entiers t au hasard
trie le tableau à l'aide de la méthode sort() .
génère un entier x au hasard
insère ensuite l'entier x à sa place dans le tableau, c'est à dire de façon à ce que le tableau soit toujours trié après insertion de x. Mais l'utilisation de sort() est maintenant interdite.
affiche le nouveau tableau.

Un code possible.

<!DOCTYPE html>
<html lang="fr">
    <head>
        <meta charset="utf-8">
        <title> Insertion en ordre </title>
    </head>
    <body>
    
         
        <script>
        // on définit un tableau vide  :  
        let t = [];
        // on tire au hasard la longueur du tableau entre 5 et 20 :
        let longueur = Math.floor(Math.random() * 16) + 5;
        
        for(let i = 0; i < longueur; i++) {
        	// ajout d'un entier pris au hasard entre 1 et 200 : 
        	t.push( Math.floor(Math.random() * 200 ) + 1 );
        }
        
        document.write("Le tableau initial : " + t);
        // tri du tableau :
        t.sort(  (a, b)  => a - b );
        document.write('<br>');
        document.write("Le tableau trié : " + t);
        document.write('<br>');
        document.write('<hr>');
        
        let x  = Math.floor(Math.random() * 200 ) + 1; // génère un entier au hasard (même plage que les autres valeurs)
         
        
        document.write("Valeur de x : " + x + "<br>");
        document.write('<hr>');
        
        // création d'une variable initialisée par un tableau vide
        // contiendra le nouveau tableau
        let tt = [];
         
        
        for(let valeur of t) {
        	if ( valeur < x ) tt.push(valeur); 
        }
        tt.push(x);
        for(let valeur of t) {
        	if ( valeur >= x ) tt.push(valeur);
        }
         
        t = tt;
        
        document.write("Tableau final : " + t);
         
        </script>
    </body>
</html>

Dans le code précédent, on parcourt deux fois le tableau pour placer x, ce qui est une perte de temps, il serait préférable d'arrêter la première boucle dès qu'on dépasse x et reprendre la seconde là où l'on a stoppée.

Une façon de mieux contrôler la boucle sera d'utiliser une boucle while.

On peut également utiliser break. C'est ce que nous faisons ci-dessous. break a pour effet de stopper la boucle.

<!DOCTYPE html>
<html lang="fr">
    <head>
        <meta charset="utf-8">
        <title> Insertion en ordre </title>
    </head>
    <body>
  
        <script>
        // on définit un tableau vide  :  
        let t = [];
        // on tire au hasard la longueur du tableau entre 5 et 20 :
        let longueur = Math.floor(Math.random() * 16) + 5;
        
        for(let i = 0; i < longueur; i++) {
        	// ajout d'un entier pris au hasard entre 1 et 200 : 
        	t.push( Math.floor(Math.random() * 200 ) + 1 );
        }
        
        document.write("Le tableau initial : " + t);
        // tri du tableau :
        t.sort( (a, b) => a - b );
        document.write('<br>');
        document.write("Le tableau trié : " + t);
        document.write('<br>');
        document.write('<hr>');
        
        let x  = Math.floor(Math.random() * 200 ) + 1; // génère un entier au hasard (même plage que les autres valeurs)
         
        
        document.write("Valeur de x : " + x + "<br>");
        document.write('<hr>');
        
        // création d'une variable initialisée par un tableau vide
        // contiendra le nouveau tableau
        let tt = [];
         
        
        let i;
        
        for(i = 0; i < t.length; i += 1)  {
        	if ( t[i] < x) {tt.push(t[i]);}
        	else {break;}
        }
        
        tt.push(x);
        
        for(let k = i; k < t.length; k += 1)  {
        	tt.push(t[k]);
        }
         
        t = tt;
        
        document.write("Tableau final : " + t);
         
        </script>
    </body>
</html>

Tri régularité.

Situation 1

On dispose d'un tableau de résultats (notes sur 20).


t =  [ [12,15], [7,13], [17,19], [2, 12], [3, 18],[19,2], [20, 12]  ]

On veut trier ces résultats par ordre croissant de régularité.

On se donne ici le critère suivant : des résultats réguliers sont des résultats à amplitude faible (amplitude : différence entre la note la plus haute et la note la plus basse).

Écrire un script triant les résultats ci-dessus.

Situation 2

Reprendre l'exercice précédent mais avec plus de deux notes par élèves :


t =  [ [12,15,11], [7,13,14], [17,19,18], [2, 12,10], [3, 18,13],[19,2,17], [20, 12,18]  ]

Avec deux notes

<!DOCTYPE html>
<html lang="fr">
    <head>
        <meta charset="utf-8">
        <title>   ordre </title>
    </head>
    <body>
      
        <script>
        //   tableau des notes  :  
        let t =  [ [12,15], [7,13], [17,19], [2, 12], [3, 18],[19,2], [20, 12]  ];
        
        // tri croissant de régularité , c'est à dire ici par ordre décroissant d'amplitude
        
        t.sort( (a,b) => Math.abs(b[1]-b[0]) - Math.abs(a[1]-a[0])  )
        document.write("Contenu du tableau après tri   : "); 
        for(let notes of t) {
        	document.write( "[" + notes + "]; " );
        }
        </script>
    </body>
</html>

Cas deux

<!DOCTYPE html>
<html lang="fr">
    <head>
        <meta charset="utf-8">
        <title>  ordre </title>
    </head>
    <body>
    
        
        <script>
        // on définit un tableau vide  :  
        let t =  [ [12,15,11], [7,13,14], [17,19,18], [2, 12,10], [3, 18,13],[19,2,17], [20, 12,18]  ];
        
        function amplitude(tab) {//retourne l'amplitude du tableau tab
        	let ampli = 0;
        	for(let i = 0; i < tab.length-1 ; i += 1) {
        		for(let j = i+1; j < tab.length; j += 1) {
        			let ecart = Math.abs( tab[j] - tab[i] );
        			if (ecart > ampli ) {ampli = ecart;}
        		}
        	}
        	return ampli;
        } 
         
         
        t.sort(  (a,b) => amplitude(b)-amplitude(a) );
        
        document.write("Contenu du tableau après tri   : "); 
        for(let notes of t) {
        	document.write( "[" + notes + "]; " );
        }
        </script>
    </body>
</html>