기수 정렬은 비교 정렬(버블, 삽입, 선택 퀵, 합병)들과 다릅니다. 두 요소를 가지고 비교하는 정렬이 아닙니다. 대신에, 숫자의 크기에 대한 정보를 자릿수로 인코딩하여 비교하는 정렬입니다. 숫자의 자리수가 많다는 것은 큰 숫자임을 의미합니다.

진수의 크기만큼에 버킷이 있다고 가정을 하고 그 버킷에 숫자를 넣고 빼는것을 반복하여 정렬을 하게 됩니다.

0~9 까지의 버킷이 존재하고, 숫자를 1의 자리 수 부터 시작해서 해당하는 버킷에 담습니다.

예를 들어 [123,90,2,1,56]이 있다면
0번 버킷 => 90
1번 버킷 => 1
2번 버킷 => 2
3번 버킷 => 123
6번 버킷 => 56

이렇게 담은 숫자를 0부터 차례대로 빼서 재정렬 하게 됩니다.

[90, 1, 2, 123, 56]
이번에는 10의 자리 숫자를 봅니다.
0번 버킷 => 1, 2
2번 버킷 => 123
5번 버킷 => 56
9번 버킷 => 90

차레대로 뺀 뒤 반복합니다.

[1, 2, 123, 56, 90]
이번에는 100의 자리 숫자입니다.
0번 => 1, 2, 56, 90
1번 => 123

재정렬 하게 되면,
[1, 2, 56, 90, 123]

끝입니다!

코드로 구현하기

• 숫자 배열을 받는 함수가 있다
• 그런 다음 가장 큰 수가 몇 자리인지 알아내야 한다
• k=0 부터 가장 큰 자리수 크기만큼 반복문을 돌린다.
  • 반복을 할때마다 0부터 9까지의 버킷을 만든다
  • 숫자의 k번째 숫자를 보고 적절한 버킷에 담는다.
• 기존 배열의 버킷의 값으로 교체한다. (순서를 정렬하는 과정)
• 배열을 반환한다.

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([123,345,9067,12,98512,2345,55])

Big-O

시간 복잡도
최고 - O(nk)
평균 - O(nk)
최악 - O(nk)

공간 복잡도 - O(n+k)