Radix Sort - 기수 정렬

목차

기수 정렬 : 소개
기수 정렬 : helper 메소드
기수 정렬 : 의사코드
기수 정렬 : 구현
기수 정렬 : 빅오 복잡도

---

기수 정렬 : 소개

https://visualgo.net/en/sorting

 

1. 기수 정렬은 숫자 리스트에서 작용하는 특수 정렬 알고리즘이다.
2. 결코 요소들을 비교하지 않는다!
3. 숫자의 크기는 자릿수로 결정된다.
4. 자릿수가 많을수록 숫자가 커진다!

기수 정렬 : helper 메소드

기수 정렬을 구현하려면 먼저 몇 가지 헬퍼함수를 만드는 것이 좋다.

getDigit(num, place) 는 주어진 place인자의 값에 해당하는 num인자의 값을 반환한다. (자릿수에 해당하는 값 리턴)

getDigit(12345, 0); // 5
getDigit(12345, 1); // 4
getDigit(12345, 2); // 3
getDigit(12345, 3); // 2
getDigit(12345, 4); // 1
getDigit(12345, 5); // 0

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

실행순서

Math.abs(12345) => 12345

Math.pow(10, 4) => 10000

Math.floor(12345 / 10000) => 1

1 % 10 => 1

 

digitCount(num)은 num 인자의 자릿수를 반환한다.

digitCount(1); // 1
digitCount(25); // 2
digitCount(314); // 3

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

 

digitCount(1234) 실행순서
1. Math.abs(1234); // 1234
2. Math.log10(1234); // 3.091315159697223
3. Math.floor(3.091315159697223) // 3
4. 3 + 1 // 4

 

mostDigits(nums)는 숫자 배열을 인자로 받고, 배열안에서 가장 큰 숫자의 자릿수를 리턴한다.

mostDigits([1234, 56, 7]); // 4
mostDigits([1, 1, 11111, 1]); // 5
mostDigits([12, 34, 56, 78]); // 2

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

mostDigits([1, 11, 111, 1111, 11111]); // 5  실행순서

i 가 0일 때: maxDigits === 1,
i 가 1일 때: maxDigits === 2,
i 가 2일 때: maxDigits === 3,
i 가 3일 때: maxDigits === 4,
i 가 4일 때: maxDigits === 5 (5 자릿수)

 

기수 정렬 : 의사코드

1. 숫자 목록을 받는 함수(radixSort)를 정의한다.
2. 가장 큰 숫자가 몇 자릿수 인지 알아낸다. (최대 자리수(mostDigits) 메소드 사용)
3. 2번값이 만약 4라면, 루프를 4 번(0부터 1, 2, 3 진행) 수행한다.
4. 반복문 진행  
  4-1. 각 자릿수에 버킷을 만든다. (버킷은 빈 배열이다. 하위 배열이 10(0~9)개 있는 배열이다.)
  4-2. 루프를 수행할 때마다 각각의 수를 올바른 버킷에 넣는다.
5. 기존 배열을 버킷의 값(0~9)으로 교체한다.
6. 마지막에는 목록을 반환

기수 정렬 : 구현

function getDigit(num, i) {		//🤔 getDigit(num, place) - 자릿수에 해당하는 값! 리턴
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

function digitCount(num) {		//🤔 digitCount(num) - num인자의 자릿수! 리턴
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(nums) {		//🤔 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); 	// 최대 자릿값: 4
    for(let k = 0; k < maxDigitCount; k++){ 	// 0~3 까지 4번 반복 (1, 10, 100, 1000의 자리수)
        let digitBuckets = Array.from({length: 10}, () => []);	// 길이10인 빈 배열 생성
        for(let i = 0; i < nums.length; i++){ 	// 입력된 배열 길이만큼 반복
            let digit = getDigit(nums[i],k); 	// 배열의 요소값과 k(자리값)을 헬퍼함수에 넣어서 자릿수에 해당하는 값 구함
            digitBuckets[digit].push(nums[i]); 	// 버킷배열의 인덱스자리에 nums[i] 요소 push
        }
        nums = [].concat(...digitBuckets); 	// 새로운 배열([])에 버킷배열값을 얕은복사한다.
    }
    return nums; // 최종 배열 반환.
}

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

동작순서

INPUT	[ 23, 345, 5467, 12, 2345, 9852 ]
\	0	1	2	3	4	5	6	7, 8	9
1 자리		12, 9852		23		345, 2345		5467
10 자리		12	23		345, 2345	9852	5467
100 자리	12, 23			345, 2345	5467				9852
1000 자리	12, 23, 345		2345			5467			9852
OUTPUT	[ 12, 23, 345, 2345, 5467, 9852 ]

 

기수 정렬 : 빅오 복잡도

회고
1. 병합 정렬 및 퀵 정렬은 효율적인 정렬 알고리즘이다.
2. 퀵 정렬은 최악의 경우 느릴 수 있지만 평균적으로 병합 정렬과 비슷하다.
3. 병합 정렬은 새 배열을 만들기 때문에 더 많은 메모리를 사용한다. (내부 병합 정렬은 존재하지만 실제로는 복잡하다!).
4. 기수 정렬은 숫자에 대한 빠른 정렬 알고리즘이다.
5. 기수 정렬은 선형적인 시간안에 숫자를 정렬하기 위해 자릿수를 이용한다. (고정된 자릿수의 경우에)