Radix Sort
Wed May 01 2024 Digit Extraction:
Utilizes a helper function getDigit to retrieve a specific digit of a number based on its place value. This is crucial for placing each number in the appropriate "bucket" during the sorting process.
Digit Counting:
Another helper, digitCount, determines the number of digits in a number, which is vital for knowing how many passes the sorting algorithm needs to make over the data.
Identify Maximum Digits:
The function mostDigits scans through the array to find the number with the maximum number of digits, which dictates the number of sorting passes needed.
Sorting Logic:
For each digit place starting from the least significant digit, the algorithm distributes the elements into buckets (0-9 for decimal values) based on their digit value at the current position. After each pass, the elements are collected back from the buckets, preserving the new order.
1//Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit.
2// It is an efficient sorting algorithm for integers or strings with fixed-size keys.
3let arr = [121,432, 564, 23, 1, 45, 788]
4
5function getDigit(num, place) {
6 return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
7}
8
9function digitCount(num) {
10 if (num === 0) return 1;
11 return Math.floor(Math.log10(Math.abs(num))) + 1;
12}
13
14function mostDigits(nums) {
15 let maxDigits = 0;
16 for (let i = 0; i < nums.length; i++) {
17 maxDigits = Math.max(maxDigits, digitCount(nums[i]));
18 }
19 return maxDigits;
20}
21
22function radixSort(arr) {
23 let maxDigitCount = mostDigits(arr);
24 for (let k = 0; k < maxDigitCount; k++) {
25 let digitBuckets = Array.from({length: 10}, () => []);
26 for (let i = 0; i < arr.length; i++) {
27 let digit = getDigit(arr[i], k);
28 digitBuckets[digit].push(arr[i]);
29 }
30 arr = [].concat(...digitBuckets);
31 }
32 return arr;
33}
34
35console.log(radixSort(arr));