```
-Intro to Radix Sort
-Radix Sort: Helper Methods
-Radix Sort: Pseudocode
-Radix Sort: Implementation
```

### Intro to Radix Sort

Radix sort is a special sorting algorithm that works on lists of numbers. Never makes comparisons between elements, however, exploits the fact that information about the size of a number is encoded in the number of digits. More digits means a bigger number.

Takes a list of numbers

Start looking at the first digit in the number on the right side, then the number gets grouped into a bucket based off of that number in the positon.

All numbers that have a 2 in the first right side position go in the 2 bucket, all the numbers have a 6 in the right side position go in the 6 bucket. The length of the digit does not matter. The numbers in the buckets do not have to be sorted.

Then the numbers get put back in a list in the order that they were placed in the buckets.

Then look at the 3rd digit in the new list.

### Radix Sort: Helper Methods

In order to implement radix sort, it is helpful to build a few helper functions first: getDigit(num, place) - returns the digit in num at the given place value.

#### Radix Example

```
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
mostDigits([23,567,89,12234324,90])
```

### Radix Sort: Pseudocode

Define a function that accepts a list of numbers

Figure out how many digits the largest number has

Loop from k = 0 up to this largest numbers of digits

For each iteration of the loop:

Create buckets for each digit (0 to 9)

Place each number in the corresponding bucket based on its kth digit

### Radix Sort: Implementation

```
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}
radixSort([23,345,5467,12,2345,9852])
```

## Top comments (0)