Tri Fusion en Javascript

Version imprimable

Bonjour,

Je tente d'implémenter un algorithme de tri fusion en Javascript dans "l'ardoise" de Firefox Dev Edition. J'ai un message d'erreur "out of memory". Je pense que j'ai une boucle infinie, mais je ne vois pas où.
Voici le code:

Code:

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
function triFusion(tab) {
  var rep = [];
  var tabL = tab.length;
  if(tabL < 2) {
    console.log("Tableau déjà trié, il n'y a rien à faire!" +tab);
    return tab;
  } else {
    var q = Math.ceil(tabL / 2);
    var left = triFusion(tab.slice(0,q));
    var right = triFusion(tab.slice(q+1, tabL));
    return fusion(left, right); 
  }
}
 
function fusion(tabLeft, tabRight) {
  var ans = [];
  var tabLeftL = tabLeft.length;
  var tabRightL = tabRight.length;
  var cpteurL = 0;
  var cpteurR = 0;
 
  while((cpteurL < tabLeftL) && (cpteurR < tabRightL)) {
    if(tabLeft[cpteurL] >= tabRight[cpteurR]) {
      ans.push(tabLeft[cpteurL]);
      cpteurL += 1;
 
    } else {
      ans.push(tabRight[cpteurR]);
      cpteurR +=1;
 
    }
  } 
  for(var i = cpteurL; i < tabLeftL; i++) {
    ans.push(tabLeft[i]);
  }
 
  for(var j = cpteurR; j < tabRightL; j++) {
    ans.push(tabRight[j]);
  }
 
  return ans;
}
 
var tableau = [9, 0, 1, 9, 3, 5, 4, 7, 2, 6, 4, 1, 0, 3, 9, 8, 7, 5, 1, 3, 9, 8, 5, 3, 0, 1, 3];
triFusion(tableau);

Merci pour votre aide.

01/02/2016, 18h53
Amnael

J'ai regardé vite fais, je suis pas sûr de ce que j'avance:

Il me semble que tu va sortir de ta boucle while avec des valeurs pour cpteurL et l'autre égales à la taille de ton tab.

Du coup, dans ta boucle for ton i vaut d'entrée la valeur de ton compteur et il me semble bien que tu n'entre même pas dans tes boules for et que par conséquent le tableau ans que tu renvoies est vide.

Résolu

Merci pour ta réponse. Le problème se situait au niveau de l'appel récursif, je faisais une mauvaise division du tableau; l'indice de début du second tableau n'était pas bon.
La solution:

Code:

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
function triFusion(tab) {
  var rep = [];
  var tabL = tab.length;
  if(tabL < 2) {
    //console.log("Tableau déjà trié, il n'y a rien à faire!" +tab);
    return tab;
  } else {
    var q = Math.ceil(tabL / 2);
    var left = triFusion(tab.slice(0,q));
    console.log("left: " +left);
    var right = triFusion(tab.slice(q, tabL));
    return fusion(left, right); 
  }
}
 
function fusion(tabLeft, tabRight) {
  var ans = [];
  var tabLeftL = tabLeft.length;
  var tabRightL = tabRight.length;
  var cpteurL = 0;
  var cpteurR = 0;
 
  while((cpteurL < tabLeftL) && (cpteurR < tabRightL)) {
    if(tabLeft[cpteurL] > tabRight[cpteurR]) {
      ans.push(tabLeft[cpteurL]);
      cpteurL += 1;
 
    } else {
      ans.push(tabRight[cpteurR]);
      cpteurR +=1;
 
    }
  } 
  for(var i = cpteurL; i < tabLeftL; i++) {
    ans.push(tabLeft[i]);
  }
 
  for(var j = cpteurR; j < tabRightL; j++) {
    ans.push(tabRight[j]);
  }
 
  return ans;
}
 
var tableau = [9, 0, 1, 9, 3, 5, 4, 7, 2, 6, 4, 1, 0, 3, 9, 8, 7, 5, 1, 3, 9, 8, 5, 3, 0, 1, 3];
var reponse = triFusion(tableau);
console.log("la reponse: " +reponse);