Récursion infinie en JavaScript quicksort ?

Question

Voici le quicksort le code que j'ai écrit. La fonction ne fonctionne pas car elle ne peut pas atteindre le cas de base. Si j'enregistre le pivot, r y l à la console, ils restent les mêmes, quel que soit le nombre de fois où la fonction de tri est appelée. Je me demande donc si l'argument l , r ne sont pas réellement transmises à la fonction en tant que données. Pourquoi cela s'est-il produit ?

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}

Answer 1

Je pense que le problème ici est que votre étape de partitionnement ne réduit pas nécessairement le tableau d'entrée. Par exemple, voyons ce qui se passe si vous essayez de trier [1, 2]. Dans ce cas, l'élément pivot sera l'élément 2. Puisque 1 > 2 est faux, 1 est ajouté à la liste. l . Puisque 2 > 2 est faux, 2 est ajouté à la liste l . En conséquence, votre appel récursif sur la liste l aura exactement les mêmes arguments que votre appel original, provoquant une récursion infinie.

Pour résoudre ce problème, essayez de diviser l'entrée en trois listes : une liste de valeurs plus petites, une liste de valeurs égales et une liste de valeurs plus grandes. Ce code est présenté ici :

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

Cette nouvelle version regroupe explicitement les éléments égaux dans leur propre liste, afin qu'ils ne soient pas triés récursivement par l'un ou l'autre des appels récursifs. Elle gère également de manière élégante les éléments en double.

J'espère que cela vous aidera !

Answer 2

Si vous choisissez la plus grande valeur du tableau comme élément pivot, alors toutes les valeurs de data se retrouvera dans le tableau l et aucune dans r . Ainsi, la récursion ne s'arrêtera jamais (et gardera la fonction l , r y pivot aux mêmes valeurs). A moins qu'il ne s'agisse d'un exercice cérébral, l'utilisation de data.sort() devrait faire un meilleur travail. ;)

Answer 3

JavaScript transmet les objets par référence (les tableaux sont également des objets). Si vous voulez les passer par valeur, vous devez utiliser la fonction splice comme expliqué aquí .

Notez que cela créera un grand nombre de copies de vos données. Vous voudrez probablement utiliser la fonction native sort().