RADIX SORT | 기수 정렬

Radix sort is a special sorting algorithm that works on lists of numbers

It never makes comparisons between elements!

It exploits the fact that information about the size of a number is encoded in the number of digits.

More digits means a bigger number!

두 요소를 가지고 비교하지 않습니다.
무엇이 더 작은지, 무엇이 더 큰지 묻지 않습니다.
그 대신, 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용합니다.

RADIX SORT HELPERS

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

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

RADIX SORT PSEUDOCODE

Define a function that accepts list of numbers
Figure out how many digits the largest number has
Loop from k = 0 up to this largest number 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

Replace our existing array with values in our buckets, starting with 0 and going up to 9
return list at the end!

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

console.log([].concat([[1],[2],[3]])) //[ [ 1 ], [ 2 ], [ 3 ] ]
console.log([].concat(...[[1],[2],[3]])) //[ 1, 2, 3 ]

RADIX SORT BIG O

Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
O(nk)	O(nk)	O(nk)	O(n + k)

n - length of array
k - number of digits(average)

Recap

Merge sort and quick sort are standard efficient sorting algorithms
Quick sort can be slow in the worst case, but is comparable to merge sort on average
Merge sort takes up more memory because it creates a new array (in-place merge sorts exist, but they are really complex!)
Radix sort is a fast sorting algorithm for numbers
Radix sort exploits place value to sort numbers in linear time (for a fixed number of digits)