📚기수정렬

숫자를 비교를 하지않는 정렬 알고리즘
숫자 크기에 대한 정보를 자릿수로 인코딩한다는 것을 이용해 정렬

예시

기수 정렬 알고리즘을 적용할 배열

1. 1의 자리수 기준으로 분류
   즉, 902 는 10^0 의 자리숫자가 2이기 때문에 2번 버킷으로 분류

2. 분류된 버킷을 기준으로 순서대로 정렬후 10^1의 자리수를 기준으로 버킷 분류
   

3. 위 과정 반복 10^2의 자리수 버킷 분류

4. 10^3의 자리수 버킷 분류

5. 배열 정렬 완료!
   

기수정렬에 필요한 코드

1. 자리수 파악 함수 : 10^i 자리수가 0 ~ 9 중에 어떤 숫자인지 확인

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

Ex) getDigit(1234, 2)

1. 1234 / 10^2 : 12.34
2. 12.3 % 10 : 2.3
3. Math.floor(2.3) : 2

2. num이 몇 자리수 인지 확인하는 함수 : 3번 함수에 사용할 거임

fuction digitCount(num) {
  if (num === 0 ) return 1;
  return Math.floor(Math.log10(Math.abs(num)) + 1;
}

Ex) digitCount(423)

1. Math.log10(423) + 1 : 3.62634
2. Math.floor : 3

3. 정렬을 몇 번 반복해야하는지 파악하는 함수 : nums배열에서 최대 자릿수 찾기

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

현재 digits와 nums[i]의 digits을 비교해 가장 큰 digits를 찾는 함수

4. 기수정렬 함수

fuction radixSort(nums){
  // 버킷 분류를 몇 번해야하는지 파악
  let maxDigitCount = mostDigits(nums);
  
  // 분류 반복문
  for (let k = 0; k < maxDigitCount; k++) {
    // 0 ~ 9 숫자 담을 수 있는 배열 형태의 digitBukets 선언
    let digitBukets = Array.from({length : 10}, () => [])
    // nums 각 요소의 자릿수에 맞는 버킷에 push
    for (let i = 0; i < nums.length; i++) {
      digitBukets[getDigit(nums[i], k)].push(nums[i]);
    }
    // digitBukets 각 요소를 spread 문법으로 풀어서 concat
    nums = [].concat(...digitBukets);
  }
  return nums;
}

최종 코드

// 1. 자리수 파악
const getDigit = (num, i) => {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

// 2. 정렬을 몇 번 반복해야하는지 파악 : 가장 큰 숫자의 자릿수 찾기
const digitCount = (num) => {
    if (num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num))) + 1;
}

// 3. 배열에서 최대 자릿수 찾기
const mostDigits = (nums) => {
    let maxDigits = 0;
    for (let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
    return maxDigits; 
}

// 4. 기수 정렬 함수
const radixSort = (nums) => {
    let maxDigitCount = mostDigits(nums);
    for (let k = 0; k < maxDigitCount; k++){
        let digitBukets = Array.from({length:10}, () => [])
        for (let i = 0; i < nums.length; i++){
            digitBukets[getDigit(nums[i], k)].push(nums[i]);
        }
        nums = [].concat(...digitBukets);
    }
    return nums;
}

console.log(radixSort([23, 345, 5467, 12, 2345, 9852]))