[Udemy] 기수정렬(Radix Sort)

1. 개념

a. 정수의 자리수를 이용하여 각 요소간 비교를 하지 않고 요소들을 정렬한다.

b. 참고로 이때까지 공부했던 정렬들은 모두 비교 정렬이다. 비교 정렬의 최상의 케이스에서 시간복잡도는 O(n log n)이다. 기수정렬은 비교를 하지 않으므로 속도가 매우 빠르다(시간복잡도: O(log n) )

2. 로직(getDigit)

a. 자릿수 별로 숫자 알아내기(getDigit)

        i. 숫자를 받아서 문자열로 변환 후 각 인덱스 별로 버킷으로 구분하기. 문자열의 인덱스가 앞에서부터 시작하는 게 문제. =>음수 인덱스 사용해서 해결할 수는 있다. 또한 문자열을 다시 숫자로 바꿔줘야 한다.
        ii. 또는 10진수임을 활용해 10, 10^2, 10^3 등으로 나누어가면서 계산해서 구하는 방법이 있다.

b. 가장 큰 숫자의 자리수 알아내기(digitCount)

        i. 버킷에 숫자를 몇 번 담아야 하는지 알아야 한다. 배열 에서3452가 가장 큰 수라면 버킷에 수를 4번 담아서 확인한다. 1의 자리수 한 번, 10의 자리수 한 번, 100의 자리 수 한 번, 1000의 자리 수 한 번.

c. b에서 구한 값을 loop의 조건문으로 설정하고, 각 자리 수를 순회하면서 정렬을 한다. 111과 22를 비교한다고 하면, 10의 자리수를 비교할 때까지는 22가 111보다 앞에 정렬되지만, 100의 자리수를 비교하면 111이 앞에 오게 된다.

3. 코드

/* 기수정렬 */
/* 각 자리수의 값을 구하는 함수 */
function getDigit(number, digit) {
  const exponentiation = 10 ** digit;
  return Math.floor(number / exponentiation) % 10;
}
/* 자리수 구하기 */
function digitCount(number) {
  return String(number).length;
  //return Math.floor(Math.log10(Math.abs(number))) + 1
}
/* 최대 자리수 구하기 */
function mostDigit(array) {
  let maxDigit = 0;
  for (let i = 0; i < array.length; i++) {
    maxDigit = Math.max(maxDigit, digitCount(array[i]));
  }
  return maxDigit;
}
/* 
기수정렬 의사코드
1. 배열에서 가장 큰 수의 자릿수 a 반환
2. k = 0부터 a까지 bucket 생성
    1) bucket은 빈배열이며 0부터 9까지 하위 배열이 10개 있는 배열
    2) loop를 수행할 때마다 각 수를 버킷에 저장
3.  */
function radixSort(array) {
  let maxLoop = mostDigit(array);
  for (let i = 0; i < maxLoop; i++) {
    /* array의 요소들을 자리수 별로 담을 배열 생성.배열 안에 배열10개가 있다. */
    let bucketArray = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < array.length; j++) {
        /* 각 자리의 값을 구함. i가 0이면 1의자리의 수, 1이면 10의자리 수를 구해서
        bucketArray의 index 배열에 담는다. 값이 5면 bucketArray[5]에 push하는 것. */
      let digit = getDigit(array[j], i);
      bucketArray[digit].push(array[j]);
    }
    /* loop를 한 바퀴 돌 때마다 정렬이 된다. */
    array = [].concat(...bucketArray);
    console.log(array);
  }
  return array;
}
console.log(radixSort([111, 2, 3333, 4, 55]));

4. TIL

    a. Array.from()과 Array().fill의 차이(이중 배열일 때)
        i. 자릿수별로 10개의 하위배열에 넣으려고 했더니 인덱스에 맞게 들어가는 게 아니라 하위 배열 전부 push가 되었다. 알고보니 Array().fill을 사용해서 그런 것이다..
        ii. fill로 만든 이중 배열은 배열 속의 배열들이 모두 같은 주소로 할당된다. 그래서 모두 동일한 배열이 만들어 지는 것이다.. 

        let Array1 = Array.from({ length: 4 }, () => []);
        let Array2 = Array(4).fill([]);
        Array1[0].push(1);
        Array2[0].push(1);
        console.log(Array1, Array2);

이런 차이가 난다. 윗 줄에 출력된 배열은 Array1이고, 아래 줄에 출력된 배열은 Array2다. 나는 인덱스 0번에 있는 배열에 값을 넣었는데도, fill로 만든 array에서는 하위 배열 모두에 값이 저장된다.