[알고리즘👽] 11. 기수정렬(Radix sort)

기수 정렬: 소개 (Radix sort)

지금까지 살펴 본 모든 정렬들은 비교 정렬 알고리즘이라는 그룹에 속한다. 그 의미는 이렇습니다. 버블 정렬에 대해 다루거나, 더 발전된 퀵 정렬을 다루더라도 결국 본질적으로 기본 비교는 주어진 시점에서 두 개의 항목을 비교한다. 한 항목은 왼쪽에 있고, 하나는 오른쪽에 있으며 정렬 방식에 따라 어느것이 먼저 오고 나중에 올지 결정합니다.

그러므로 비교 정렬은 두 가지 비교한다는 의미이다. 더 작은 것과 더 큰 것을 비교한 다음에 항목의 위치를 결정합니다.

문제는 비교 정렬보다 더 나은 방법이 있을까요? O(n log(n))에서 더 나아질 수 있을까요? 더 좋아질 수 있나요? 답은 yes입니다. 하지만 비교를 통한 방법이 아니다.

수학적으로, 비교 정렬의 평균 시간 복잡도에서 하한선과 접근선이 존재한다. 특정 케이스에서만 작동하는 비교 알고리즘이 아닌 정렬 알고리즘 유형이 있다. 이러한 알고리즘은 데이터의 특별한 속성을 이용한다.

예를 들어, 정수 정렬 알고리즘이라는 정렬 그룹이 있다면 정수로만 수행된다. 직접 비교하지 않는다는 말의 의미는 실제로 이 숫자가 이 숫자보다 작은가? 이 숫자가 이 숫자보다 큰가? 하는 비교를 하지 않는다는 것이고 다른 방식으로 데이터를 정렬하게 됩니다.

그래서 기수 정렬은 비교를 수행하지 않기 때문에 재밌고, 지금까지 다룬 것과 아주 다르다.

기수정렬

비교를 수행하지 않는 특별한 정렬 알고리즘이고 숫자로 작동한다. 보통, 실제로 사용할 때 이진수를 이용합니다. 어떤 숫자든 이진법으로 표현할 수 있죠. 그리고 원하는 문자열이나 이미지를 가져와 이진 형식으로 바꿀 수도 있습니다. 그래서 다른 데이터를 정렬할 수 있죠. 하지만 정렬할 때 사용할 실제 데이터는 숫자여야 합니다. 그리고 950이나 17과 같은 십진법 숫자를 사용할 겁니다.

두 요소를 무엇이 더 큰 지 작은 지 비교하지 않는다. 그 대신, 자릿수를 확인한다. 숫자 크기에 대한 정보를 자릿수로 인코딩한다는 사실을 이용한 결과다. 예를 들어 네자릿수가 두자릿수보다 크다, 이런 식으로만 확인한다.

 

기수 정렬: helper 메소드

1. 자릿수 알아내기 (getDigit)
2. function getDigit(num, i) { return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10; }
3. 전체 목록에서 자릿수가 가장 많은 수를 알아내기
4. function digitCount(num) { if (num === 0) return 1; return Math.floor(Math.log10(Math.abs(num)) + 1; }
5. 자릿수 최대값 알아내기(maxDigits)
6. function mostDigits(nums) { let maxDigits = 0; for (let i = 0; i < nums.length; i++) { maxDigit = Math.max(maxDigits, digitCout(nums[i])); } return maxDigits; }

기수 정렬: 의사코드

• 배열을 받는 함수를 정의한다
• 가장 큰 수가 몇 자리인지 알아낸다
• 0부터 가장 큰 자리수까지 루프를 돌린다
  • 각 자리수마다 버킷을 만든다
  • 다음 루프를 수행할 때마다 각각의 수를 올바른 버킷에 넣기

기수 정렬: 구현

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

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

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(nums){
    let maxDigitCount = mostDigits(nums);
    for(let k = 0; k < maxDigitCount; k++){
        let digitBuckets = Array.from({length: 10}, () => []);
        for(let i = 0; i < nums.length; i++){
            let digit = getDigit(nums[i],k);
            digitBuckets[digit].push(nums[i]);
        }
        nums = [].concat(...digitBuckets);
    }
    return nums;
}

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

기수 정렬: 빅오 복잡도

n은 정수이고 k는 길이이다. 자릿수가 긴 수가 있으면 영향을 미친다. k 자리에 logn은 넣으면 nlogn이 된다. 평균적으로 k가 log n이라서 더 좋다. 이론적으로 더 빠른 건 맞다. 하지만 컴퓨터 메모리에 수를 저장하는 방식에 대한 제한으로 인해 실제로는 그렇지 않을 수 있으며 비교 정렬과 마찬가지일 수 있다.