기수 정렬(Radix sort)

기수 정렬이란?

Radix sort is a special sorting algorithm that works on lists of numbers
It never makes comparisons between elements!
It exploits the fact that information about the size of a number is encoded in the number of degits
More digits means a bigger number!

기수 정렬은 앞서 살펴본 정렬들과 다른 특징을 가지고 있다. 앞서 살펴본 정렬은 다른 값들과 비교를 통해 정렬을 하지만 기수 정렬은 기수 즉, 자릿수를 가지고 정렬을 한다. 이말은 다른 값과 비교를 하지 않는다는 것이다. 자릿수를 가지고 정렬이 가능한 이유는 자릿수가 클 수록 그리고 특정 자릿수에서 어떤 위치에 값이 존재하는지를 파악해도 대소비교가 가능하다는 것이다.

기수 정렬은 버킷을 사용한다. 버킷이란 바구니로 값들을 넣어두는 공간이다. 10진법일 경우 0부터 9까지의 버킷이 있고 5진법인 경우 0부터 4까지의 버킷이 있다. 이러한 버킷을 각 자리수에서 사용하게 된다.

2-1. 기수 정렬의 간단한 예시

배열 [1556, 4, 3556, 593, 408, 4386, 902, 7, 8157, 86, 9637, 29]을 오름차순으로 정렬하자.

일의 자리 버킷을 만든다.
- 0: []
- 1: []
- 2: [902]
- 3: [593]
- 4: [4]
- 5: [8157]
- 6: [1556, 3556, 4386, 86]
- 7: [7, 9637]
- 8: [408]
- 9: [29]
일의 자리 버킷을 기준으로 재정렬한다.
- [902, 593, 4, 8157, 1556, 3556, 4386, 86, 7, 9637, 408, 29]
십의 자리 버킷을 만든다.
- 0: [902, 4, 7, 408]
- 1: []
- 2: [29]
- 3: [9637]
- 4: []
- 5: [8157, 1556, 3556]
- 6: []
- 7: []
- 8: [4386, 86]
- 9: [593]
십의 자리 버킷을 기준으로 재정렬한다.
- [902, 4, 7, 408, 29, 9637, 8157, 1556, 3556, 4386, 86, 593]
백의 자리 버킷을 만든다.
- 0: [4, 7, 29, 86]
- 1: [8157]
- 2: []
- 3: [4386]
- 4: [408]
- 5: [1556, 3556, 593]
- 6: [9637]
- 7: []
- 8: []
- 9: [902]
백의 자리 버킷을 기준으로 재정렬한다.
- [4, 7, 29, 86, 8157, 4386, 408, 1556, 3556, 593, 9637, 902]
천의 자리 버킷을 만든다.
- 0: [4, 7, 29, 86, 408, 593, 902]
- 1: [1556]
- 2: []
- 3: [3556]
- 4: [4386]
- 5: []
- 6: []
- 7: []
- 8: [8157]
- 9: [9637]
천의 바리 버킷을 기준으로 재정렬을 하면서 정렬을 마무리한다.
- [4, 7, 29, 86, 408, 593, 902, 1556, 3556, 4386, 8157, 9637]

2. 기수 정렬의 의사 코드

2-1. helper 의사 코드

먼저, 어떤 숫자의 특정 자리수의 값을 반환하는 helper 의사 코드를 먼저 만들어보자. 0부터 시작한다. 즉, 0이 일의 자리를 뜻한다.

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

그 다음으로 필요한 helper는 특정 수에 자릿수가 얼마나 되는지를 알 수 있는 함수이다. 예를들어, 421이라는 숫자의 자릿수가 3이라는 것을 알려주는 것이 필요하다. 이를 통해 버킷에 몇 번을 정렬해야 하는지 알 수 있다.

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

하나의 숫자의 자리수를 구하는 helper를 작성해보았다. 이번엔 요소가 숫자인 배열에서 가장 큰 자리수를 구하는 helper를 만들어보자.

function mostDigits(arr) {
  const digits = [];
  arr.forEach((num) => digits.push(digitCount(num)));

  return Math.max(...digits);
}

이전 정렬 알고리즘과 다르게 helper 함수가 많이 필요하다!

2-2. 기수 정렬의 전체 의사 코드

function radixSort(arr) {
  const maxDigit = mostDigits(arr);

  for (let i = 0; i < maxDigit; i++) {
    const bucket = [[], [], [], [], [], [], [], [], [], []];
    arr.forEach((num) => {
      const digitNum = getDigit(num, i);
      bucket[digitNum].push(num);
    });
    arr = bucket.flat();
  }

  return arr;
}

먼저, 위의 코드는 내가 직접 기수 정렬 코드를 구현한 것이다.

function radixSort(nums) {
  let maxDigitCount = mostDigits(nums);
  for (let i = 0; i < maxDigitCount; i++) {
    let digitBuckets = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < nums.length; j++) {
      let digit = getDigit(nums[j], i);
      digitBuckets[digit].push(nums[j]);
    }
    nums = [].concat(...digitBuckets);
  }

  return nums;
}

위는 강의에서 작성한 기수 정렬 코드이다. 전체적인 알고리즘의 흐름은 같다. 먼저 최대 자리수를 찾고 찾은 최대 자리수만큼 반복문을 돌린다. 각각의 반복문에서 bucket를 만들고 배열 안의 요소를 반복문을 돌린다. 특정 자라수의 값을 바탕으로 올바른 버킷에다 넣고 반복문이 끝나면 버킷을 합치는 과정을 반복한다.

하지만 다른 점도 분명 존재한다.

버킷을 만드는 과정 난 단순하게 배열을 모두 만들었다..ㅎㅎ 하지만 강의에서는 Array.from()이라는 멋진 메서드를 사용하여 만들고 있다.
반복문 난 for 문 뿐 아니라 배열의 고차함수도 사용했지만 강의에서는 모두 for 문만 사용했다.
버킷 합치기 난 flat() 메서드를 강의에선 concat() 메서드를 사용한다.

3. 기수 정렬의 시간 복잡도

시간 복잡도(Best)

시간 복잡도(Average)

시간 복잡도(Worst)

공간 복잡도

O(nk)

O(n + k)

k라는 특별한 상수가 붙여진 것을 볼 수 있다. 기수 정렬 입장에서 볼 땐 k가 바로 최대 자리수에 해당된다. 때문에 최대 자리수 크면 클수록 시간 복잡도는 높아진다. 때문에 이를 무시할 순 없다.

기수 정렬의 시간 복잡도를 본다면 다른 정렬 알고리즘보다 빠르다고 할 수 있다. 하지만 컴퓨터 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 그렇지 않을 수도 있다.

4. Conclusion

매우 재미있는 알고리즘이었다. 지금까지 정렬이라고 하면 다른 값과 비교하여 자리를 찾아가는 것이라는 생각만 했는데, 기수 정렬은 자리수의 값을 가지고 이를 재정렬하는 것이기 때문에 다른 값과의 비교는 하지 않는다. 숫자라는 개념에 대한 원초적인 특징에 대해서 많은 생각을 하게되었다. 이런 점이 후에 문제를 다양하게 접근할 수 있는 실마리가 될 거 같다!

📅 2023-02-06

Previous퀵 정렬(Quick Sort)NextData structure(자료구조)

Last updated 1 year ago