Mélanger un tableau sans sort

**mathieu** · 16/11/2022, 15h56

Je suis à la recherche d'une discussion sur le forum ici qui expliquait pourquoi il ne faut pas utiliser sort pour mélanger un tableau mais après 30 minutes je ne l'ai pas trouvée.

Dans mes archives, j'ai juste retrouvé le code à utiliser à la place :

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function melange(tableau)
{
 
	let i, j, element;
 
	i = tableau["length"];
 
	while (i > 1) {
 
		j = Math.floor(Math.random() * i--);
 
		element = tableau[i];
		tableau[i] = tableau[j];
		tableau[j] = element;
 
	}
 
 
	return tableau;
 
}

et j'ai aussi le code qui permet de faire la comparaison et où on voit que le mélange avec "sort" n'est pas du tout équilibré :

Code html :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
<script>
 
function melange_DECONSEILLE(tableau)
{
        return tableau.sort(e => 0.5 - Math.random());
}
 
 
function melange_PAS_RAPIDE(tableau)
{
        var i;
        var j;
        var index;
        var tableau2;
 
        index = {};
        tableau2 = [];
        i = tableau.length;
        while (--i>=0) {
                
                while (index[j = Math.floor(Math.random()*tableau.length)]===true) {}
                index[j]=true;
                tableau2[i]=tableau[j];
                
        }
        
        
        return tableau2;
        
}
 
 
function melange_ACCEPTABLE(tableau)
{
        var i;
        var j;
        var tableau2;
 
        tableau2 = [];
        i = tableau.length;
        while (--i >= 0) {
                
                tableau2[i] = tableau[j = Math.floor(Math.random()*(i+1))];
                tableau.splice(j,1);
                
        }
        
        
        return tableau2;
        
}
 
 
function melange_TROP_BIEN(tableau)
{
        
        let i, j, element;
        
        i = tableau["length"];
        
        while (i > 1) {
                
                j = Math.floor(Math.random() * i--);
                
                element = tableau[i];
                tableau[i] = tableau[j];
                tableau[j] = element;
                
        }
        
        
        return tableau;
        
}
 
 
//////////////////////////////////////////////////////////////////////////////////////////////////
// comparaison des méthodes
 
function test(fonction_melange)
{
        let tableau;
        let valeurs = ["A", "B", "C"];
        
        console.time(fonction_melange);
        
        let verification = {};
        let i = 100000 * fact(valeurs["length"]);
        
        while (--i >= 0) {
                
                tableau = window[fonction_melange]([...valeurs]);
                
                verification[tableau] = !(tableau in verification) ? 1 : verification[tableau] + 1;
                
        }
        
        console.timeEnd(fonction_melange);
        
        affiche_resultat(verification);
        
}
 
function affiche_resultat(verification)
{
        
        let cles = [];
        let somme = 0;
        
        
        for (const cle in verification) {
                cles.push(cle);
                somme += verification[cle];
        }
        
        let moyenne = Math.floor(somme / cles.length);
        
        cles.sort();
        
        cles.forEach(cle => {
                
                let diff = verification[cle] - moyenne;
                
                console.log(cle + " : " + verification[cle] + " (" + diff + ", " + (diff / moyenne * 100).toFixed(1) + " %)");
                
        });
        
        
        console.log("=== moyenne : " + moyenne + " ===");
        
        
}
 
function fact(nbr) 
{
        // Si nbr = 0 la factorielle retournera 1
        if (nbr === 0) {
                return 1;
        }
        // appelez à nouveau la procédure récursive
        return nbr * fact(nbr - 1);
}
 
 
test("melange_DECONSEILLE"); // mélange déséquilibré
test("melange_PAS_RAPIDE");  // performances : risquées, toutes les combinaisons possibles : oui, probabilités identiques : oui.
test("melange_ACCEPTABLE");  // performances : moyennes, toutes les combinaisons possibles : oui, probabilités identiques : oui.
test("melange_TROP_BIEN");   // performances : bien,     toutes les combinaisons possibles : oui, probabilités identiques : oui.
 
 
</script>

Donc si quelqu'un sait comment retrouver cette discussion, ça permettrai de rendre à César ce qui lui appartient.
Ou alors si vous savez expliquer pourquoi l'utilisation de sort produit cela, lancez vous

**NoSmoking** · 16/11/2022, 17h54

Bonjour,
peut-être fais tu allusion à :

Cartes aléatoires avec code qui ne fonctionne qu'à moitié.

ou encore à :

Placements aleatoires images

... il faut regarder du côté des interventions de Loralina

**mathieu** · 16/11/2022, 18h23

on avance en effet, dans la 2e discussion se trouve le code de test des différents algorithmes.

mais j'ai l'impression qu'il y avait encore un autre message qui expliquait que "sort" fait des permutations ou quelque chose comme ça. et là je viens de commencer à regarder dans la liste des messages de Loralina mais je n'ai pas encore trouvé.

**SpaceFrog** · 17/11/2022, 10h01

Une autre piste ?
https://javascript.developpez.com/ac...re-simplifiee/

**NoSmoking** · 17/11/2022, 10h30

Envoyé par mathieu

mais j'ai l'impression qu'il y avait encore un autre message qui expliquait que "sort" fait des permutations ou quelque chose comme ça

pourrais-tu préciser, l'algo de sort est défini dans ECMAScript® 2023 Language*Specification

**mathieu** · 17/11/2022, 13h12

Envoyé par NoSmoking

pourrais-tu préciser

justement je ne sais plus quel mots étaient utilisé, j'ai fait des recherches sur "tri mélange shuffle" et je ne l'ai pas retrouvé.

Envoyé par NoSmoking

l'algo de sort est défini dans ECMAScript® 2023 Language*Specification

quand on déroule ça, on arrive au point 5 qui indique que l'algorithme tri est défini par une "source externe" donc ça dépend peut-être des navigateurs ?
https://tc39.es/ecma262/multipage/in...exedproperties

**NoSmoking** · 17/11/2022, 18h46

Il me semble effectivement qu'à une époque cela dépendait du navigateur, son moteur JS, mais je ne pense plus que ce soit le cas.

Par contre on peut encore lire sur MDN : Différences d'implémentation.

Concernant les sources pour FireFox j'ai retrouvé ceci

c'est un peu en vrac ... si cela te dit !

Pas fait la recherche pour Chrome.

Mélanger un tableau sans sort

JavaScript

Discussions similaires

Partager

Partager