[JS / 알고리즘] 기수 정렬 radix sort

참고
영상으로 이해하기 : https://visualgo.net/en/sorting

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴하라.

주의사항

• 기수 정렬 써라
• arr.sort 사용 금지

기수정렬?

작은 자리 수 부터 정렬을 시키는 것이다.

처음엔 1의 자리 숫자만 가지고 정렬을 시킨다.

그리고 그 정렬를 가진 채 10의 자리 숫자만 따져서 정렬한다.

마지막 자리인 10^3의 자리 숫자까지 반복하면 완성이다.

핵심포인트

1.getDigit

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

각 자리에 해당하는 숫자가 무엇인지 알아내는 함수가 필요

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

math.abs : 절대값 구하는
math.pow : 10에 i제곱한 수

예를들어 getDigit(1234,3) 이면

Math.abs(num) / Math.pow(10,i)) % 10

1234 / 1000 % 10

1.234 % 10 = 1.234

Math.floor(1.234) = 1

따라서 getDigit(1234,3) = 1 로직이다.

2. digitCount

각 숫자의 자리수를 알아내는 코드

문자로 변환시켜서 길이를 반환하면 된다.

function digitCount(num) {
	return num.toString().length;
    }

3. mostDigits

배열 내에서 가장 자리수가 긴 숫자의 길이 구하기

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(arr) {

	// 요소 중 가장 긴 자리 수 구하기
	const maxDigits = mostDigits(arr);
    
    // 0~ 가장 긴 자리 수 까지 반복
    for(let k = 0 ; k < maxDigits; k++) {
      // 각 자리수에 해당하는 숫자를 담을 그릇 만들기
    	let digitBuckets = Array.from({length:10}, () => []);
      
      // 각 요소를 맞는 그릇에 담기
        for(let i = 0 ; i < arr.length ; i++) {
        	let digit = getDigit(arr[i], k);
            digitBuckets[digit].push(arr[i]);
            }
      //각 그릇에 담긴 값들을 합쳐서 배열로 만들어야
            arr = [].concat(...digitBuckets);
            }
            return arr;
}