DEV Community

Code_Regina
Code_Regina

Posted on

1

Radix Sort

                   -Intro to Radix Sort
                   -Radix Sort: Helper Methods
                   -Radix Sort: Pseudocode
                   -Radix Sort: Implementation
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

Alt Text

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

Alt Text

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

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





Enter fullscreen mode Exit fullscreen mode

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









Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up