Radix Sort

All of the sorts that we've seen so far our groups together in a group called comparioson sorting algorithms. All that means is that whether we're talking about bubble sort or something more advanced like quicksort at the end of the day beneath the surface the base comparison that we're doing is between two items at any given point. So we have one item on the left let's say and another on the right and we're deciding which one comes first, or which one comes second depending on how we're sorting. So comparison sort just means we're comparing two things. That's the most we ever compare at a given time. We're doing less than vs greater than and then we're deciding where that one item goes.

As we saw earlier.

Average Time Complexity

Bubble Sort => O(n^2) Insertion Sort => O(n^2) Selection Sort => O(n^2) Quick Sort => O(n log n) Merge Sort => O(n log n)

So the question is => are there faster sorter algorithms? Can we do better? => The answer is Yes we can but not making compariosons => there lots of other sorting algorithms some of them are slower => But the best average case time complexity that we can ever hope for in any comparison sort is n log n

Now we have a solution here => we have a way around this but only in certain cases => so there are other type of sorting algorithms, that are not comparison algorithms, and these algorithms and these algorithms take advantage of special properties of the data, for example there is a group of sorts called integer sorting algorithms and they only work with integers with numbers. and we don't actually make direct comparisons. One of those is Radix Sort

When I say that we don't make direct comparisons, I mean we're never actually comparing is this number less than this number, is this number greater than this number, so we end up sorting the data in a different way

So Radix Sort is kind of fun and it's very different than anything we've done so far, because we're not making comparisons

Radix Sort

1. Radix Sort is a special sorting algorithm that works on lists of numbers. So usually when this is actually used it's used with binary numbers and the number can be expressed in binary, also you could take any strings or images if you wanted to and convert them to binary. So it's possible to sort other data but the actual data we work with at the time, that we're sorting it needs to be numbers.

2. It never makes compariosons between elements! instead it exploits the fact that information about the size of a number is encoded in the number of digits. What it means => More digits means a bigger number!

How does it work?

we take a list of numbers and we create 10 different buckets and these buckets represent all of the possible numbers. the one digit numbers in base ten. So 0 through 9. and what we do => is we go through the entire list of numbers and we start by looking at first digit, and we group them into buckets based off of that number.

Radix Sort Helpers?

In order to implement radix sort, it's helpful to build a few helper functions first:

getDigit(num, place) => returns the digit in num at the given place value

getDigit(12345, 0); // 5
getDigit(12345, 1); // 4
getDigit(12345, 2); // 3
getDigit(12345, 3); // 2
getDigit(12345, 4); // 1
getDigit(12345, 5); // 0

getDigit.js

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

digitCount(num) => returns the number of digits in num

digitCount(1); // 1
digitCount(13); // 2
digitCount(134); // 3

We'll use this to find largest number in the entire list

digitCount.js

function digitCount(num) {
  if (num === 0) return 1;

  return Math.floor(Math.log10(math.abs(num))) + 1;
}

mostDigits.js

mostDigits(nums) => Given an array of numbers, returns the number of digits in the largest numbers in the list

mostDigits([1234, 56, 7]); // 4
mostDigits([1,1, 11111, 1]); // 5
mostDigits([22, 56, 33]); // 2

mostDigits.js

function mostDigits(nums) {
   let maxDigits = 0;
   for (let i = 0; i < nums.length; i++) {
     maxDigits = Math.max(maxDigits, digitCount(nums[i]));
   }
   return maxDigits;
}

Radix Sort Pseudocode

1. Define a function that accepts a list of numbers
2. figure out how many digits the largest number has
3. Loop from k = 0 up to this largest number of digits
4. 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
5. Replace our exisiting array with values in our buckets, starting with 0 and going up to 9
6. return list at the end!

Radix Sort implementation

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 = getDigits(nums[i], k);
      digitBuckets[digit].push(nums[i]);
    }
    nums = [].concat(...digitBuckets);
  }
  return nums;
}

Radix Sort Big O

Time Complexity (Best) => O(nk)

Time Complexity (Average) => O(nk)

Time Complexity (Worst) => O(nk)

Time Complexity (Best) => O(n + k)