Implementado un Radix Sort que ordena una lista de números. Aquí está mi código:
function getDigit(number, index, lengthOfLongestNumber) { let numberString = number.toString(); numberString = numberString.padStart(lengthOfLongestNumber, '0'); return parseInt(numberString[index], 10) || 0; } function getLengthOfLongestNumber(numbers) { // return Math.floor(Math.log10(Math.max(...numbers))) + 1; let largestNumber = 0; for (let i = 0; i < numbers.length; i++) { if (numbers[i] > largestNumber) { largestNumber = numbers[i]; } } return largestNumber.toString().length; } function radixSort(numbers) { const lengthOfLongestNumber = getLengthOfLongestNumber(numbers); for (let i = lengthOfLongestNumber - 1; i >= 0; i--) { const buckets = new Array(10).fill().map(() => []); while (numbers.length) { const number = numbers.shift(); buckets[getDigit(number, i, lengthOfLongestNumber)].push(number); } for (let j = 0; j < 10; j++) { // numbers = numbers.concat(buckets[j]); ---> uncomment this line and comment out the following while loop // numbers = [...numbers, ...buckets[j]]; ---> or uncomment this line and comment out the following while loop while (buckets[j].length) { numbers.push(buckets[j].shift()); } } } return numbers; } Las pruebas fallan cuando fusiono una matriz de buckets en una matriz de numbers usando concat() en la función radixSort (dentro del bucle for interno). Pero de alguna manera pasa si uso while loop en su lugar.
Puede ver y ejecutar pruebas en CodeSandbox .
¿Por qué está pasando esto? ¿Cuál es la diferencia entre ellos que hace que las pruebas fallen?
Para la matriz devuelta , no importa cuál de esas alternativas use, pero si las pruebas esperan que ordene la matriz dada , de modo que después de la llamada, la matriz de entrada se haya ordenado por sí misma , entonces, de hecho, las alternativas comentadas serán no trabajo. Esto se debe a que esas alternativas asignan numbers en lugar de mutarlos.
Simplemente verifique la diferencia entre las alternativas al ignorar la matriz devuelta, pero mirando la matriz dada:
let arr = [521, 219, 100, 422, 889, 529, 491, 777, 641, 882, 229]; radixSort(arr); console.log(arr);Las alternativas comentadas registrarán una matriz vacía.
La versión correcta muta numbers y no le asigna una matriz (nueva).
Para evitar el bucle, también puedes hacer esta mutación así:
numbers.push(...buckets[j]); E incluso puede reemplazar el bucle for alrededor de esa declaración, con solo esta línea:
numbers.push(...buckets.flat());