기수정렬(Radix sort)

기수 정렬은 자릿수를 기반으로 정렬한다.

가령 숫자의 일의 자리, 십의 자리, 백의 자리와 같은 자릿수이다. 당연히 두 자리 숫자는 한 자리 숫자보다 크고 세 자리 숫자보다 작다.

보통 기수 정렬은 10진수를 기반하여 설명하고 사용하지만 원리를 이해하면 다른 진법에서도 적극적으로 활용하 수 있다.

 

기수 정렬의 작동 순서

• 1단계: 가장 작은 자릿수부터 가장 큰 자릿수까지 반복하여 비교한다.(값 그 자체가 아니라 자릿수를 비교함에 주의)
• 2단계: 각 자릿수를 기준으로 입력 배열을 정렬한다.
• 3단계: 각 자릿수별로 정렬된 배열을 합쳐 정렬을 완료한다.

function radixSort(arr) {
    // 최대값 찾기
    const maxNum = Math.max(...arr);
    
    // 현재 자릿수 (1의 자리부터 시작)
    let exp = 1;
    
    // 최대값의 자릿수만큼 반복
    while (Math.floor(maxNum / exp) > 0) {
        countingSort(arr, exp);
        exp *= 10;
    }
    
    return arr;
}

function countingSort(arr, exp) {
    const n = arr.length;
    
    // 결과 배열
    const output = new Array(n).fill(0);
    
    // 카운트 배열 (0-9 숫자를 카운트)
    const count = new Array(10).fill(0);
    
    // 현재 자릿수를 기준으로 카운트
    for (let i = 0; i < n; i++) {
        const digit = Math.floor(arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // 카운트 배열 업데이트하여 실제 위치 계산
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 뒤에서부터 배치하여 안정성 유지
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // 원래 배열에 복사
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 사용 예시
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("정렬 전:", arr);
radixSort(arr);
console.log("정렬 후:", arr); // [2, 24, 45, 66, 75, 90, 170, 802]

// 더 큰 배열로 테스트
const bigArray = [432, 8, 530, 90, 88, 231, 11, 45, 677, 199];
console.log("큰 배열 정렬 전:", bigArray);
radixSort(bigArray);
console.log("큰 배열 정렬 후:", bigArray);

 

 

만약 입력 배열이 1부터 999까지 숫자가 무작위로 있는 경우라면, 가능한 자릿수는 3가지(일, 십, 백)뿐이다. 1단계에서 주어진 입력 배열을 순회하며 숫자의 자릿수에 따른 배열에 저장한다. 다만 최댓값을 모르는 경우라면 최댓값을 기준으로 자릿수별 배열을 만들어야 하므로 최댓값을 찾는 함수가 필요하다.

 

// 입력 배열의 최댓값
function findMax(arr) {
  let max = arr[0];
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

// 기수 정렬
function radixSort(arr) {

  // 최댓값을 찾는 함수를 사용하여 입력 배열의 최댓값을 찾는다.
  const max = findMax(arr);

  // 자릿수별 기수 정렬: exp는 1,10,100,1000,10000,100000,1000000,...
  function countingSort(arr, exp) {
    const count = new Array(10).fill(0);
    const output = new Array(arr.length);
    /*
    new Array(arr.length)
    메모리는 할당했지만 값이 할당되지 않은 "빈" 슬롯을 가진 배열생성
    이런 빈 슬롯은 undefined와도 다르다.map, forEach 등의 메서드에서 건너뛴다.
    */

    for (let i = 0; i < arr.length; i++) {
      // 자릿수로 배열 원소를 나눈 몫을 10으로 나눠 나머지를 구한다.
      const digit = Math.floor(arr[i] / exp) % 10;
      count[digit]++;
    }    
    /*
    자바스크립트에서는 모든 숫자가 부동 소숫점(double)으로 처리된다.
    정수 나눗셈과 실수 나눗셈으로 구분하지 않기 때문에 항상 실수 결과를 반환한다.
    만약 정수값을 얻고 싶다면 Math 라이브러리의 메서드를 사용해야 한다.
    */

    for(let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    for(let i = arr.length - 1; i >= 0; i--) {
      const digit = Math.floor(arr[i] / exp) % 10;
      output[count[digit] - 1] = arr[i];
      count[digit]--;
    }

    for(let i = 0; i < arr.length; i++) {
      arr[i] = output[i];
    }
  }

  // 가장 큰 자릿수부터 시작하여 기수 정렬을 반복적으로 수행하는 함수
  function radixSortUtil(arr) {
    const len = arr.length;
    const maxDigit = Math.floor(Math.log10(max)) + 1; //최대 자릿수

    for(let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
      // 여기서 함수 사용
      countingSort(arr, exp);
    }
  }

  radixSortUtil(arr);
  return arr;
  
}

console.log(radixSort([19,3, 999, 788733,2,23,323,4]))
/*
[ 2, 3, 4, 19, 23, 323, 999, 788733]
*/

 

 

아래처럼 개선할 수 있다.

 

function radixSort(arr) {
    const countingSort = (arr, exp) => {
        // 정렬된 결과를 저장할 임시 배열
        const output = new Array(arr.length).fill(0);
        // 0-9 각 자릿수의 개수를 저장할 배열
        const count = new Array(10).fill(0);

        // 현재 자릿수(exp)를 기준으로 각 숫자의 발생 횟수를 세기
        arr.forEach((num) => {
            const digit = Math.floor(num / exp) % 10;
            count[digit]++;
        })

        // 누적 합 계산 - 이는 각 숫자의 최종 위치를 결정하는데 사용됨
        // 예: count[2]가 3이면, 2는 정렬된 배열에서 인덱스 2까지 차지
        for (let i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 뒤에서부터 순회하며 안정적 정렬 수행
        // 뒤에서부터 하는 이유: 안정적 정렬을 위해 (같은 숫자의 상대적 순서 유지)
        for(let i = arr.length - 1; i >= 0; i--) {
            const digit = Math.floor(arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 정렬된 결과를 원본 배열에 복사
        output.forEach((num, i) => {
            arr[i] = num;
        })
    }

    const max = Math.max(...arr);
    const maxDigit = Math.floor(Math.log10(max)) + 1;

    // exp는 1, 10, 100, 1000... 순으로 증가
    // max/exp > 0 조건은 모든 자릿수를 처리할 때까지 반복
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
    return arr;
}

 

 

구체적 예시를 들어 로직을 쉽게 나타내면 아래와 같다. 

나머지 값을 사용하여 한 자리로 만들어 비교한다. 그리고 순서를 정렬하여 원본배열에 적용한다. 자릿수를 올려(1, 10, 100... 순으로) 나머지 배열을 만들어 한 자리 수끼리 비교하여 배열을 정렬한다. 이걸 또 다시 원본배열에 적용한다.  

 

결국 기수 정렬의 핵심은:

1. 큰 수를 한 자리수로 쪼개서 비교
2. 그 결과를 원본 배열에 반영
3. 자릿수를 올려가며 반복

이다.

원본 배열: [23, 45, 12, 36, 42, 97]

1. 1의 자리 정렬
나머지 값: [3, 5, 2, 6, 2, 7]
크기 비교: 2 < 2 < 3 < 5 < 6 < 7
정렬 결과: [12, 42, 23, 45, 36, 97]  
// 2로 끝나는 수들(12,42) 
// 3으로 끝나는 수(23) 
// 5로 끝나는 수(45)
// 6으로 끝나는 수(36)
// 7로 끝나는 수(97) 순으로 정렬

2. 10의 자리 정렬
나머지 값: [1, 4, 2, 3, 4, 9]  // 12, 42, 23, 36, 45, 97의 10의 자리
크기 비교: 1 < 2 < 3 < 4 < 4 < 9
최종 결과: [12, 23, 36, 42, 45, 97]  
// 1x대(12)
// 2x대(23)
// 3x대(36)
// 4x대(42,45) - 1의 자리에서 이미 2<5로 정렬됨
// 9x대(97) 순으로 정렬

 

 

아래 부분은 각 자릿수에서 0부터 9까지의 숫자가 각각 몇 번 나오는지 세는 과정이다.

 

// 현재 자릿수(exp)를 기준으로 각 숫자의 발생 횟수를 세기
        arr.forEach((num) => {
            const digit = Math.floor(num / exp) % 10;
            count[digit]++;
        })
        
  // 초기 배열: [23, 45, 12, 36, 42, 97]

// 1의 자리 정렬 (exp = 1)
Math.floor(23 / 1) % 10 = 23 % 10 = 3  // count[3]++
Math.floor(45 / 1) % 10 = 45 % 10 = 5  // count[5]++
Math.floor(12 / 1) % 10 = 12 % 10 = 2  // count[2]++
Math.floor(36 / 1) % 10 = 36 % 10 = 6  // count[6]++
Math.floor(42 / 1) % 10 = 42 % 10 = 2  // count[2]++
Math.floor(97 / 1) % 10 = 97 % 10 = 7  // count[7]++

// count 배열: [0,0,2,1,0,1,1,1,0,0]
// 의미: 2가 2개, 3이 1개, 5가 1개, 6이 1개, 7이 1개
// 1의 자리 기준 정렬 후: [12, 42, 23, 45, 36, 97]
// (2로 끝나는 숫자들, 3으로 끝나는 숫자들... 순으로 정렬됨)

// 10의 자리 정렬 (exp = 10)
Math.floor(12 / 10) % 10 = 1 % 10 = 1  // count[1]++
Math.floor(42 / 10) % 10 = 4 % 10 = 4  // count[4]++
Math.floor(23 / 10) % 10 = 2 % 10 = 2  // count[2]++
Math.floor(45 / 10) % 10 = 4 % 10 = 4  // count[4]++
Math.floor(36 / 10) % 10 = 3 % 10 = 3  // count[3]++
Math.floor(97 / 10) % 10 = 9 % 10 = 9  // count[9]++

// count 배열: [0,1,1,1,2,0,0,0,0,1]
// 의미: 1이 1개, 2가 1개, 3이 1개, 4가 2개, 9가 1개
// 최종 정렬 결과: [12, 23, 36, 42, 45, 97]
// (10의 자리가 1인 숫자, 2인 숫자... 순으로 정렬됨)

이렇게 각 자릿수에서 어떤 숫자(0-9)가 몇 번 나오는지를 count 배열에 기록하는 것다. 이 정보는 나중에 숫자들을 정렬된 위치에 배치하는데 사용된다.

 

 

아래는 1의 자리 한 바퀴를 도는 것을 설명한 것이다. 똑같은 나머지가 나와서 같은 인덱스를 가리키더라도, 앞서 -- 연산으로 값을 감소시켰기 때문에 가리키는 것보다 하나 앞의 원소를 가리키게 된다. 이것이 안정 정렬을 유지하는 핵심 로직이라고 할 수 있다. 

 

예를 들어 i가 4일 때와 i가 2인 경우 모두 count[2]인 원소를 가지게 된다. 그러나 i가 4였을 때 이미 값을 감소시켰기 때문에 output[1]이 아니라 하나 앞선 output[0]을 가리키게 되고 여기에 arr[2]인 12가 할당된다.

 

사실상 이 로직을 실행하기 위해 누적합을 적용한 배열인 [0,0,2,3,3,4,5,6,6,6]을 만들었던 것이다. 이 로직이 적용되기 전까지 [0,0,2,3,3,4,5,6,6,6] 배열은 아무런 의미도 없다. 누적합은 따로 정리가 필요할 것 같다.

원본 배열: [23, 45, 12, 36, 42, 97]

1) count 배열 생성 (각 자릿수 개수)
[0,0,2,1,0,1,1,1,0,0]

2) 누적합 계산
[0,0,2,3,3,4,5,6,6,6]

3) 뒤에서부터 output 배열 채우기:

i=5) 97 처리
- 나머지 7 → count[7]=6 → output[5]=97
output=[0,0,0,0,0,97]
- count[7]-- → 5가 됨

i=4) 42 처리
- 나머지 2 → count[2]=2 → output[1]=42
output=[0,42,0,0,0,97]
- count[2]-- → 1이 됨

i=3) 36 처리
- 나머지 6 → count[6]=5 → output[4]=36
output=[0,42,0,0,36,97]
- count[6]-- → 4가 됨

i=2) 12 처리
- 나머지 2 → count[2]=1 → output[0]=12
output=[12,42,0,0,36,97]
- count[2]-- → 0이 됨

i=1) 45 처리
- 나머지 5 → count[5]=4 → output[3]=45
output=[12,42,0,45,36,97]
- count[5]-- → 3이 됨

i=0) 23 처리
- 나머지 3 → count[3]=3 → output[2]=23
output=[12,42,23,45,36,97]
- count[3]-- → 2가 됨

 

 

아래 부분에 대해서

[23, 45, 12, 36, 42, 97]
1의 자리: [3, 5, 2, 6, 2, 7]

// 1. 각 숫자의 개수를 센다
count = [0,0,2,1,0,1,1,1,0,0]
// 인덱스: 0 1 2 3 4 5 6 7 8 9
// 의미: 
// count[2] = 2 : 2로 끝나는 숫자가 2개 (12, 42)
// count[3] = 1 : 3으로 끝나는 숫자가 1개 (23)
// count[5] = 1 : 5로 끝나는 숫자가 1개 (45)
// count[6] = 1 : 6으로 끝나는 숫자가 1개 (36)
// count[7] = 1 : 7로 끝나는 숫자가 1개 (97)

만약 위와 같다면 정렬된 결과는 이렇게 되어야 한다:
[12, 42, 23, 45, 36, 97]
↑   ↑
0   1 위치에 2로 끝나는 숫자들

왜냐하면:
1. 1의 자리 기준으로 정렬하면
  - 2로 끝나는 숫자가 가장 작으므로(2,3,5,6,7 중) 가장 앞에 와야 함
  - 2로 끝나는 숫자가 2개니까 0,1 위치를 차지
  - 그 다음 3으로 끝나는 숫자가 2번 위치
  - 그 다음 5로 끝나는 숫자가 3번 위치
  ...이런 식으로 정렬됨

그리고 나서

 

배열: [23, 45, 12, 36, 42, 97]
count: [0,0,2,3,3,4,5,6,6,6]

/*
		for(let i = arr.length - 1; i >= 0; i--) {
            const digit = Math.floor(arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 정렬된 결과를 원본 배열에 복사
        output.forEach((num, i) => {
            arr[i] = num;
        })

의 내용이 함축돼 있다.
*/

뒤에서부터 순회:
1. i=5: 97 처리
   - digit = 7
   - output[count[7]-1] = output[6-1] = output[5] = 97
   - count[7]-- (6->5)

2. i=4: 42 처리
   - digit = 2
   - output[count[2]-1] = output[2-1] = output[1] = 42
   - count[2]-- (2->1)

3. i=3: 36 처리
   - digit = 6
   - output[count[6]-1] = output[5-1] = output[4] = 36
   - count[6]-- (5->4)

4. i=2: 12 처리
   - digit = 2
   - output[count[2]-1] = output[1-1] = output[0] = 12
   - count[2]-- (1->0)

5. i=1: 45 처리
   - digit = 5
   - output[count[5]-1] = output[4-1] = output[3] = 45
   - count[5]-- (4->3)

6. i=0: 23 처리
   - digit = 3
   - output[count[3]-1] = output[3-1] = output[2] = 23
   - count[3]-- (3->2)

최종 output: [12, 42, 23, 45, 36, 97]

 

 

 

여기까지가 1의 자리였고 점차 10, 100의 자리로 올라가며 순회한다.

---

 

기수정렬은 자릿수를 비교하는 개념이기 때문에 정수에 적용하면 탁월하다. 그러나 문자열 정렬에도 사용할 수 있다. 반대로 자릿수가 없는 부동 소숫점 실수와 같은 경우엔 기수 정렬이 불가하다. 또한 자릿수별로 임시 배열을 저장할 때 공간 복잡도가 발생하는 점 역시 고려해야 한다.

 

기수 정렬은 중첩 없는 반복들로 구성된다. 이러한 이유에서 O(kn)의 복잡도를 가지며 k는 자릿수가 몇 개나 있는지를 의미한다.

기수 정렬은 안정 정렬에 해당하며, 비교 연산이 없어 자릿수를 기준으로 정렬하기 때문에 일반적인 알고리즘보다 좋은 성능을 보여준다. 입력 데이터에 제약이 있으니 데이터 세트의 형식을 고려해야 한다.

 

 

 

 

 

예제1)

/*
노력왕 선발대회:

한 고등학교에서 성적과 무관하게 공부를 오랫동안 학생에게 특별상을 주고자 한다.
이 고등학교는 학생이 매년 몇 시간 공부했는지 기록했고, 학년, 반, 번호 순으로 나열했다.
그러나 이 학교는 학생 수가 많아서 기존으 방식으로는 순서를 매기기 어려웠다.

기수 정렬을 이용해 해결하자.
*/

function radixSort(arr, key) {
 // 최댓값을 구하고 한 자릿수를 더 늘려서(* 10), 
 // while 루프가 모든 자릿수를 처리할 수 있도록 보장
 let maxNum = Math.max(...arr.map((obj) => obj[key])) * 10;
 let divisor = 10;
 
 // divisor가 최대값보다 작은 경우 반복
 while (divisor < maxNum) {
   // [ [],[],[],[],[],[],[],[],[],[] ] ]
   let buckets = [...Array(10)].map(() => []);
   
   // 각 숫자의 특정 자릿수를 추출하여 해당 버킷에 분류하는 과정
   // 예: divisor가 100일 때는 십의 자리, 1000일 때는 백의 자리를 추출
   for(let num of arr) {
     // 1. num[key] % divisor로 현재 처리할 자릿수보다 큰 자릿수들을 제거
     // 2. divisor / 10으로 나누는 이유: 앞에서 곱한 10을 다시 나눠서
     //    현재 자릿수의 값(0-9)를 얻기 위함
     buckets[Math.floor((num[key] % divisor) / (divisor / 10))].push(num);
   }
   
   // 2차원 배열을 평탄화 하여 1차원 배열로 만든다. [].concat(...buckets), buckets.flat() 과 같다. 
   arr = [].concat.apply([], buckets);
   // 자릿수 올리기
   divisor *= 10
 }
 return arr
}

/*
[
  { grade: 3, class: 1, number: 1, studyTime: 30 },
  { grade: 2, class: 1, number: 1, studyTime: 60 },
  { grade: 2, class: 2, number: 2, studyTime: 80 },
  { grade: 1, class: 2, number: 1, studyTime: 90 },
  { grade: 2, class: 2, number: 1, studyTime: 100 },
  { grade: 2, class: 1, number: 2, studyTime: 110 },
  { grade: 1, class: 1, number: 1, studyTime: 120 },
  { grade: 1, class: 2, number: 2, studyTime: 130 },
  { grade: 1, class: 1, number: 2, studyTime: 150 }
]
*/

 

 

기수 정렬은 문자열에도 적용이 가능하다. 방법은 문자열을 정수로 바꾼 후 기수 정렬을 통해 정렬하고 다시 문자열로 변환하면 된다.

 

• 문자열 -> 정수
• 정수를 이용해 정렬
• 정수 -> 문자열

예제2)

/*
문자열 받아서 정렬하기
*/

// 문자를 숫자로 변환하는 함수
function convertToNumeric(str) {
  const numericArr = [];
  for (let i = 0; i < str.length; i++) {
    numericArr.push(str.charCodeAt(i));
  }
  return numericArr;
  // console.log(convertToNumeric("AaZz")); // [ 65, 97, 90, 122 ]
}

// 입력 배열에서 가장 긴 문자열의 길이를 구하는 함수
function getMaxStringLength(arr) {
  let maxLen = 0;
  for (let i = 0; i < arr.length; i++) {
    if(arr[i].length > maxLen) {
      maxLen = arr[i].length;
    }
  }
  return maxLen;
}

// 기수 정렬 함수
function radixSortString(str) {
  let arr = [...str];
  const maxLen = getMaxStringLength(arr);

  for (let i = maxLen - 1; i >= 0; i--) {
    countingSortString(arr, i);
  }
  return arr;
    // return arr.join('');  // 'abc' 형태로 재구성해서 반환하는 경우
}

// 문자열의 특정 자릿수를 기준으로 계수 정렬하는 함수
function countingSortString(arr, pos) {
  const output = new Array(arr.length).fill('');
  // // 각 문자의 빈도수를 저장하는 배열
  // const count = new Array(256).fill(0); //ASCII 문자 범위에 따라 적절 크기로 설정
  // 한글을 비롯한 유니코드까지 받는 경우
  const count = new Array(65536).fill(0); // Unicode 범위로 변경


  for (let i = 0; i < arr.length; i++) {
    const charCode = (pos < arr[i].length) ? arr[i].charCodeAt(pos) : 0;
    count[charCode]++;
  }

  // 누적합 만들기
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // 안정 정렬을 만들기 위해 뒤부터 순회
  for(let i = arr.length - 1; i >= 0; i--) {
    const charCode = (pos < arr[i].length) ? arr[i].charCodeAt(pos) : 0;
    output[count[charCode] - 1] = arr[i];
    count[charCode]--; // 동일한 값에 대해서 이전 원소에 할당해주기 위해 감소시킴
  }

  for(let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
} 

console.log(radixSortString("azrrdbasdf"))
console.log(radixSortString("안녕하세요!"))

/*
['a', 'a', 'b', 'd', 'd', 'f', 'r', 'r','s', 'z']
[ '!', '녕', '세', '안', '요', '하' ]

*/

/*
charCodeAt은 문자의 유니코드를 반환하는 함수로 String타입의 프로토타입 메서드이다.
한글을 비롯하여 유니코드에 저장된 문자는 문자 순서에 맞춰 순차적으로 값을 배정 받았다.
즉, 유니코드순으로 정렬하면 그것이 곧 가나다 순 정렬이 된다.

유니코드는 AC00등과 같은 형태로 값이 배정되었는데, 이는 16진수로 표기됐기 때문이다.
charCodeAt은 문자를 입력받아 16진수 형태의 유니코드 값을 10진수로 변환해 반환한다.


-------------

65536(2^16)은 유니코드(Unicode)의 기본 다국어 평면(Basic Multilingual Plane, BMP)의 크기다.
이는 다음과 같은 범위를 커버다:

ASCII: 0 ~ 127 (영문자, 숫자, 기본 특수문자)
확장 ASCII: 128 ~ 255
한글: 가(0xAC00) ~ 힣(0xD7A3) (약 11,172자)
기타 다국어 문자들
*/