Tri récursif dans JS

Votre code échouera si nous avons des éléments en double à cause de cette ligne. if (newLast

Il entrera en récursion infinie

function sort(arr) {
	if (arr.length === 2) {
  	const v1 = arr[0];
    const v2 = arr[1];
    const isGreater = (
    	(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
      (isNumber(v1) && isNumber(v2) && v1 > v2)
    );
  	return isGreater ? [ v2, v1 ] : [ v1, v2 ];
  } else {
  	const last = arr.pop();
    const ret = sort(arr);
    const newLast = ret.peekLast();
    debugger;
    if (newLast < last) {
      return [ ...ret, last ];
    } else {
    	return sort( [ last, ...ret ] );
    }
  }
}

function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }

//console.log(sort([1,2,3,4,5]))

console.log(sort([3,3,5,2]))

Je pense que la plupart des intervieweurs s'attendent à ce que vous répondiez par quicksort ou merge sort (ou les deux) étant donné cette question. Parmi les deux, le tri rapide est plus facile à retenir et à recréer à la rigueur car l'étape de fusion du tri par fusion est facile à gâcher.

Quicksort est un très bel algorithme et convient parfaitement aux outils fonctionnels de javascript. Cela vaut vraiment la peine de comprendre si vous allez faire des interviews:

const arr = [6, 1, 5, 3, 9, 6, 7, 10, 16, 4, 0, 12, 2]

function qsort(arr){
    if (arr.length < 2) return arr
    // choose a pivot, p
    // the choice of pivot can effect worst-case performance
    // for this, we'll just use the first element.
    const [p, ...rest] = arr

    // partition array into element greater and lesser that the pivot
    // this can be optimized so you don't loop through the array twice
    const low  = rest.filter(n => n <= p)
    const high = rest.filter(n => n > p)

    // recurse on both partitions and reassemble as recursion unwinds
    return [...qsort(low), p, ...qsort(high)]
}
console.log(qsort(arr).join(', '))

Je vois une veine de création de valeur intermédiaire qui n'est pas sans conséquence.

1. peekLast appelle Array.prototype.slice qui fait une copie du tableau. Vous copiez un tableau entier juste pour renvoyer le dernier élément.

   Array.prototype.peekLast = function () { return this.slice().pop(); }
   Array.prototype.peekLast = function () { return this[this.length]; }
   

   Cela vous donne le même résultat à chaque fois sans avoir besoin de copier.

2. L'utilisation d'arguments de propagation dans des expressions telles que [... arr, x] copie arr entièrement.

   arr.concat ([x]) fait la même chose sans faire de copie (ou de mutation) de arr

Vous appelez peekLast et utilisez ... x une fois par élément dans l'entrée. L'appel de sort sur une liste de seulement 100 éléments copiera plus de 10 000 éléments, rien que pour ces opérations. Une liste de seulement 1 000 éléments copiera plus de 1 000 000 éléments. De la place pour l'amélioration des algorithmes? Bien sûr.

Mark Meyer vous lance du bon pied. Si vous utilisez la récursivité, il est préférable d'écrire votre programme dans un style fonctionnel, car il donnera les meilleurs résultats. Mélanger le style impératif (déclarations, mutations, réaffectations, autres effets secondaires, etc.) avec la récursivité est une recette pour une migraine.

L'algorithme de Mark, aussi grand qu'une "amélioration du code" , votre question demande des "améliorations de l'algorithme" . Dans cette optique, l'algorithme de Mark souffre d'une création de valeur intermédiaire similaire en utilisant de nombreuses expressions ... x .

Une autre offense qui se cache est la double utilisation de .filter sur le même tableau, reste . Cela crée un processus inefficace car il itère entièrement à travers le repos deux (2) fois par élément . C'est un symptôme de la recherche de fonctions intégrées simples qui se rapprochent de ce que vous voulez, mais pas exactement de ce que vous voulez. Une meilleure fonction itérerait dans le tableau une fois et retournerait les deux résultats.

Les inefficacités du programme de Mark sont pour la plupart pardonnables en raison de l'amélioration spectaculaire du code qualité. Son programme est beaucoup plus lisible que le vôtre car il utilise un style fonctionnel, d'où vient la récursivité. Les inefficacités sont également très faciles à corriger, alors peut-être que c'est un exercice pour vous?

Voyons voir si cela stimule votre cerveau. Nous verrons les réponses que d'autres personnes soumettent avant de vous étouffer avec trop d'informations.