Skip to content

Instantly share code, notes, and snippets.

@fortunee
Last active April 6, 2023 02:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fortunee/93acabad8b8386f0329d10c58195fc83 to your computer and use it in GitHub Desktop.
Save fortunee/93acabad8b8386f0329d10c58195fc83 to your computer and use it in GitHub Desktop.
Radix Sort basically uses a bucket of number from 0 to 9 and groups the numbers in a given array based on the number of digits in each number
function radixSort(nums) {
const maxDigitCount = mostDigits(nums);
for (let k = 0; k < maxDigitCount; k++) {
const digitsBucket = Array.from({ length: 10 }, () => []);
for (let i = 0; i < nums.length; i++) {
const currentNum = nums[i];
const digit = getDigit(currentNum, k);
digitsBucket[digit].push(currentNum);
}
nums = [].concat(...digitsBucket);
}
return nums;
}
function getDigit(digits, position) {
return Math.floor(Math.abs(digits) / Math.pow(10, position)) % 10;
}
function digitCount(digits) {
if (digits === 0) return 1;
return Math.floor(Math.log10(Math.abs(digits))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let x = 0; x < nums.length; x++) {
maxDigits = Math.max(maxDigits, digitCount(nums[x]))
}
return maxDigits;
}
// getDigit(6053, 1);
// mostDigits([776, 65, 890, 6253, 5, 9, 4])
radixSort([776, 65, 890, 6253, 5, 9, 4])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment