[JS] 기수 정렬

1. 기수 정렬

  기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하는 배열이다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키 값의 길이만큼 기수 정렬을 반복한다. 숫자는 기본적으로 10진수로 표현되기 때문에, 키 값을 가진 원소들을 정렬할 때는 0부터 9까지 총 10 개의 버킷을 사용한다. 정렬의 반복 횟수는 입력 배열의 원소 중 최대 값의 길이 만큼이다. 예를 들어 [103, 3, 22]를 기수정렬을 이용하여 반복해야 할 때, 입력 배열 중에서는 103이 최댓값이므로, 기수 정렬의 반복횟수는 103의 길이인 3이 된다.

 

 

2. 동작 순서

 길이가 5인 입력배열 [3, 55, 7, 17, 1]을 기수정렬을 이용하여 오름차순으로 정렬하는 과정을 보면서 기수 정렬이 어떤 순서로 동작하는지 파악하도록 하자. 입력 배열 중에서 최대 값은 55다. 55의 길이는 2이므로, 기수 정렬은 총 두 번 반복한다.

 

 

 먼저, 정렬할 원소들의 일의자리 값을 추출하여 순서대로 버킷에 분배한다.

 

 

버킷에 있는 값들을 순서대로 꺼내서 저장한다.

 

 

저장한 배열의 원소들의 십의 자리 값을 추출하여 순서대로 버킷에 추출한다.

 

 

 버킷에 있는 값들을 순서대로 꺼내서 저장한다. 그러면 오름차순으로 정렬이 된 것을 볼 수 있다.

 

 

 기수 정렬의 수행시간은 어떻게 될까? 위의 예에서 정렬할 원소의 개수는 5였다. 그리고 최댓값의 길이는 2였다. 따라서 기수 정렬을 총 2번을 수행했고, 버킷에 분배하는 작업은 일의 자리 일 때는 4번, 십의 자리일 때는 3번이었다. 그러면 2*(5+4+3) = 24였다. 정렬할 원소의 수를 n으로 두고, 기수 정렬의 반복 횟수를 d, 분배작업을 r로 두면, 수행할 작업은 d(n+r)이 된다. 따라서 시간복잡도는 O(d(n+r))이다.

 

 

4. 프로그램 코드

 코드는 다음과 같다.

let arr = [69, 10, 30, 2, 16, 8, 31, 122];

const bucket = {
  '0': [],
  '1': [],
  '2': [],
  '3': [],
  '4': [],
  '5': [],
  '6': [],
  '7': [],
  '8': [],
  '9': []
}

let divider = 10;
let next = 0;
let unit = ''
let max = 1;

do{
  // 1. arr의 원소를 divider로 나누어서 문자열로 변환 
  // 2. 문자열의 첫 번째 값을 bucket 객체의 키 값과 같으면
  // 3. 키 값 속에 있는 배열로 push
    for(let i=0; i<arr.length; i++){
      if(next > 0)
        unit = '' + parseInt(arr[i]/divider);
      else{
        // 일의 자리를 비교함과 동시에 arr 배열의 원소 값의
        // 자리수를 최댓값으로 받음.
        max = Math.max(max, (''+arr[i]).length);
        unit = '' + parseInt(arr[i]%divider);
      }
      bucket[unit[0]].push(arr[i]);
    }

    // arr 빈 배열로 초기화
    arr = [];
    divider **= (++next);

    // bucket안에 있는 모든 키 값을 순서대로 꺼내서
    // arr 배열에 push
    for(let i=0; i<10; i++){
      while(bucket[`${i}`].length)
        arr.push(bucket[`${i}`].shift());
    }

}while(next<max);

console.log(arr);

 

5. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 미디어