Блог

Реализована сортировка по основаниям, которая сортирует список чисел. Вот мой код:

 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;
}
 

Тесты завершаются неудачно, когда я объединяю buckets массив в numbers массив с помощью concat() radixSort функции in (внутри внутреннего for цикла). Но это как-то проходит, если я while вместо этого использую цикл.

Вы можете просматривать и запускать тесты в CodeSandbox.

Почему это происходит? В чем разница между ними, из-за которой тесты не проходят?

Для возвращаемого массива не имеет значения, какую из этих альтернатив вы используете, но если тесты ожидают, что вы отсортируете данный массив, чтобы после вызова входной массив был отсортирован сам по себе, то действительно, закомментированные альтернативы не будут работать. Это происходит потому, что эти альтернативы назначают numbers вместо того, чтобы мутировать его.

Просто проверьте разницу между альтернативами, игнорируя возвращаемый массив, но глядя на данный массив:

 let arr = [521, 219, 100, 422, 889, 529, 491, 777, 641, 882, 229];
radixSort(arr);
console.log(arr);
 

Закомментированные альтернативы будут регистрировать пустой массив.

Правильная версия мутирует numbers и не присваивает ей (новый) массив.

Чтобы избежать петли, вы можете сделать эту мутацию также так:

 numbers.push(...buckets[j]);
 

И вы даже можете заменить for цикл вокруг этого утверждения только этой строкой:

 numbers.push(...buckets.flat());