Radix Sort
Tags: javascript, html, css, webdev
Published: 2021-02-11 05:05:49

---
title: Radix Sort  
published: true
description: 
tags: javascript, html, css, webdev
//cover_image: https://direct_url_to_image.jpg
---

                       -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 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ovtuvtqfj0fizbu6pe5f.png)

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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/d0lw84np3vpm0k59zzsq.png)

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.  

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/1xq98blr4fpnm1bom420.png)

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


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/rj5dqjuulchvkdvs9ios.png)


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


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/axtteqdkmqey58tomtt1.png)



###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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/v41hjcrro3l391rk4aw8.png)


####Radix Example 

```javascript 

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



```javascript 


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])









```